BINARY HEAP
In this blog post will study what is a binary heap, types, applications, operations and C++ code implementation for Binary Heap.
Definition
A heap is a tree with some special properties. The basic requirement of a heap is that the value of a node must be greater (or lesser) than the values of its children. This is called heap property.
A heap also has the additional property that all leaves should be at h or h – 1 levels (where h is the height of the tree) for some h > 0. That means heap should form a complete binary tree.
A heap with atmost two child nodes is called a Binary Heap. That is, a binary tree which has heap property is a binary heap.
Types
- Min Heap: The value of the parent node must be less than or equal to the values of child nodes.
- Max Heap: The value of the parent node must be greater than or equal to the values of child nodes.
The root node returns the min/max value in the heap.
Storage Represention
To represent a heap, we can use arrays instead of linked lists(as we have seen BST) because heaps will form a complete binary tree and there will be no wastage of memory.
The new nodes will be added to the heap(tree) from left leaf node to the right ones and hence we can use arrays which stores the elements in contiguous memory location.
Applications
- To implement Priority Queues efficiently.
- One of the sorting algorithms i.e. Heapsort.
- Data compression: Huffman Coding algorithm.
- Selection problem: Finding kth- smallest element.
- Shortest path algorithms: Dijkstra’s algorithm.
- Minimum spanning tree algorithms: Prim’s algorithm.
Terms
-
Heapify: After performing insert/delete
operation in heap, it may not satisfy the heap property. In
that case we need to adjust the locations of the heap to make
it heap again. This process is called heapifying. There are
two ways to heapify:
- Percolate Down: Process of heapifying from top(may be root or any other node) to bottom.
- Percolate Up: Process of heapifying from bottom to top(root).
Standard Operations
Do refer the code available the end of this section to understand the following thoery.
We shall implement binary max heap. Also I have used the word node as it is actually representing a tree but do note that the storage used is an array of data type integer and not a structure.
- Finding Parent Node: For a node at ith location, it's parent will be at the location (i-1)/2.
- Finding Child Node: For a node at ith location, it's children will be at the location (2*i) [Left child] & (2*i)+1 [Right child].
-
Percolate Down:
Get the left & right child indices and find the maximum value
among the two child.
If the maximum value is not the parent node then swap the parent node and the child node which is maximum. Percolate down again from the index which is maximum(either left or right child index).
If the parent node itself is maximum then no need of swapping and percolating again. -
Insertion:
Loop from the last element untill the new node's value is
greater than the parent node's value. Swap the parent and it's
either of child if this condition is true.
Add the new node to the index where the above condition was false and percolate down from root(index 0). -
Deletion: The maximum element i.e the root
node will be deleted and returned from the heap.
Store the first element(root) in a temporary variable, assign last element to the root and percolate down from the root(index 0).
Finally return the temporary variable(the deleted value). - Display: The traversal method used is breath first traversal and hence the elements in the array can be displayed using index starting from 0.
Code file
Please open this in your pc or with a compatible app in your mobile.
C++ Implementation for BINARY HEAPThat's it from this blog post. If you liked it then do share this blog with your friends or people who wanna get into programming world. Thank You!