Data Structure and Algorithm: Heap

Heap in  data structure and algorithm

A heap is a binary tree structure in which each member has the heap condition satisfied.

All levels in a complete binary tree are full except the last one. In particular, all levels save the last will feature two children.

The final level will be filled from the left.

Each node in the heap has a key (its value) that specifies its position in the heap.

There are two kinds of the heap in data structure

• Max- heap data structure

•    Min- heap data structure 

1. Data structure for max-heap: In a Max-Heap, the key(its value) present at the root node, P, must be the greatest among the keys present at all of its children, c (key of nodes>= key of Its children). For all subtrees of that Binary Tree, the same property must be true.

We find a non-decreasing succession of keys as we go up the tree, and a non-increasing succession of keys as we progress down the tree. To be more exact, the root contains the largest key in a max-heap.

2. The key(its value) present at the root node, let’s call it P, must be the smallest among the keys present at all of its children, let’s call it c (Key of nodes= key of its children) in a Min-Heap data structure. For all subtrees of that Binary Tree, the same property must be true recursively. We find a non-increasing series of keys as we travel up the tree, and a non-decreasing succession of keys as we progress down the tree. To be more explicit, the smallest key in a min-heap is found in the root.

Array implementation of binary heap:

An array is widely used to implement heaps. Any binary tree can be stored in an array, but a binary heap can be stored compactly because it is always a complete binary tree. Pointers don’t take up any space; instead, arithmetic on array indices can be used to get the parent and children of each node.

Let n be the number of elements in the heap, and I be any valid index in the array storing heap.

• A[0] will be the location of the root element.

The table below shows the indexes of other nodes for the ith node, A[i]:

• A[(i-1)/2] -in which the parent node A[i] is stored.

• A[(2*i)+1]- Returns the left child node.

• A[(2*i)+2]- This function returns the right child node.

Level Order is the traversal method used to achieve Array representation. 

For a max-heap: A[i]>=  A[2*i+1] and A[i] >= A[2*i+ 2]

Where, (2i+1) and (2i+2) are < n.

 As we know that in Max heap, the  key of each of the nodes are greater than the key of it’s children and hence the maximum key in the heap is stored at the root, i.e. at A[0].

For a min-heap: A[i]<=  A[2*i+1] and A[i] <= A[2*i+ 2]

Where, (2i+1) and (2i+2) are < n.

As we know that in the Min heap, the  key of each of the nodes is lesser than the key of its children and hence the minimum key in the heap is stored at the root, i.e. at A[0].

Max-heap data structure supported operation 

Max-heap supports numerous operations which is explained below:

• buildMaxHeap(A[]): This operation is used for converting an input array into max heap.

• MaxHeapify(A[], i): This operation is used to reorganise the heap’s elements while maintaining the heap property. When a node at index I generates an imbalance in the heap as a result of some operation on that node, this method is used.

• Increasekey( A[], i, v): This operation raises the value of index i in the array to value v. This method is only valid if A[i]<= v, which means that the new value is greater than the current value of index i. This ensures that the Subtree rooted at index i remains a maximum heap. The complexity of this operation is O(log n), because after increasing the key (i.e. its value) at index i the max heap property of parent(i) may be infringed, necessitating the use of some method to restore it.

• FindMax(heap[]): It returns the Max Heap’s root element. This operation has an O(1)  time complexity as it only needs to return A[0].

• extractMax(): through operating this, the maximum element is removed. The heap property must be maintained by invoking the heapify() method after removing the root, hence the time complexity of this process is O(Log n) as we replace A[0] with A[n-1], which is the least element of the heap.

• insertkey(A[],v): It requires O(Log n) time to insert a new key. At the bottom of the tree, we add a new key. We don’t need to do anything if the new key is smaller than its parent. Otherwise, we’ll have to traverse up to fix the heap property violation.

• Deletekey (A[], i): This operation is used to delete an element at index I, and hence the complexity of this operation is O(log n). To delete any element, we can replace it with the last element of the heap, and then perform the operation again to restore the heap property if it is violated in any way.

Similarly, all these operations are supported by Min-heap.

• buildMinHeap(A[])

• MinHeapify(A[], i)

• Decreasekey( A[], i, v)

• FindMin(heap[])

• extractMin()

• insertkey (A[],v)

• Deletekey (A[], i)

Application of heap in data structure: 

• Heapsort is commonly used to teach heap data structures. Because Quicksort is more practical, the heapsort algorithm has limited applications. Nonetheless, the Heap data structure is extremely popular. Other than Heapsort, the following are some uses.

• Priority Queues: Because Binary Heap allows insert(), delete(), and extract max() operations in O(logn) time, it can be used to efficiently implement priority queues. Binary Heap has two variants: Binomial Heap and Fibonacci Heap. These variations perform union in O(logn) time, which is a Binary Heap O(n) operation. Heap Priority queues are implemented in graph algorithms such as Prim’s and Dijkstra’s algorithms.

• Statistics on orders: The Heap data structure can be used to discover the kth smallest (or largest) element in an array quickly and effectively. Methods 4 and 6 are examples.

• Graph Algorithms: Some graph algorithms, such as Dijkstra’s Algorithm and Minimum Spanning Tree, utilise heaps to lower their temporal complexity.

• A heap data structure can be used to merge many already-sorted input streams into a single sorted output stream

Conclusion

A heap is a binary tree that meets the heap property and is complete or nearly complete. A parent must be equal to or more in value than the immediate children for a max-heap, and a parent must be equal to or less in value than the immediate children for a min-heap.