What are Heaps? Describe their structure.

Heaps are data structures that are based on binary trees. Heaps follow the following two rules.

1. The binary tree must be a complete binary tree. In a complete binary tree -

• Each node has a max of two child nodes.
• All intermediary nodes (all nodes except leaf nodes) are completely filled.
• The last level nodes (nodes containing children that are leaf nodes) must always contain a left child node.

2. The node must be ordered based on Heap property. Heap property can be one of the following.

• Min Heap.
• Max Heap.

What are the Heap properties used in the building of a Heap data structure?

The nodes in a Heap are build using the Heap property. Heap property can be either Min Heap or Max Heap.

Min Heap: In Min Heap the parent node keys must be less than or equal to the child node keys. Hence, in a Min Heap, the root node has the smallest key.

Max Heap: In Max Heap the parent node keys must be greater than or equal to the child node keys. Hence, in a Max Heap, the root node has the largest key.

What are the common application of Heap data structure?

Heap data structures are suitable for many applications and algorithms.

1. Sorting - Heapsort, one of the effieient sorting algorithm, uses Heap data structure.

2. Selection Algorithms - Selection algorithms use Heap data structures since min element or the max element can be accessed from a Heap in constant time. Others selections such as finding the median or the Kth element can be done in sub-linear time.

3. Graph Algorithms: Graph algorithms such as Prim's algorithm and Dijkstra's shortest-path algorithm uses Heaps as internal traversal data strctures.

4. Priority Queue: Priority Queue, an abstract data structure, is usually implemented with a Heap data structure.

5. K-Way merge: Heap data structures are used in K-Way merge where multiple sorted input streams are merged to a single output stream.

How is a Heap data structure represented in an Array?

Heap data structure is implemented using Arrays. The first element of the array contains the root node of the Heap.

The next two elements contain the two child nodes of the root. The next four elements contain the four child nodes of the two level 2 parent nodes. And so on

Building the array in above way results in the following.

• First half of the array contains the root node and intermediary nodes of the Heap
• The second half of the array contains all the leaf nodes of the Heap.

How do you insert a node in a Heap?

A node can be inserted into a Heap in the following way.

1. Add the new node at the end of the Heap at the first available place.

2. Check if the Heap property is violated.

3. If the Heap propert is violated then sift-up the new node until the heap property is established and the Heap is re-balanced. This is known as swim operation

How do you extract a node from a Heap?

When you extract from a Heap, the root node is removed and the Heap is reordered based on the Heap property.

A node can be extracted from a Heap in the following way.

1. Remove the root node and replace it with the last node of the Heap.

2. Check if the Heap property is violated.

3. If the Heap property is violated then sift-down the node until the heap property is established and the Heap is re-balanced. This is known as sink operation.

How do you replace a node from a Heap?

When you replace from a Heap, the root node is removed and replaced by the new node.

A node can be replaced from a Heap in the following way.

1. Remove the root node and replace it with the new node.

2. Check if the Heap property is violated.

3. If the Heap property is violated then sift-down the node until the heap property is established and the Heap is re-balanced (sink operation).