Heap data structure is widely use in software languages like C, C++, Python, Java etc. There are different type of heaps like Binary Heap, Fibonacci Heap, Binomial Heap and so on. Out of these, Binary Heap is more popular and others are variations of it. Following are the properties of Binary Heap.
- Binary tree property: It’s a complete tree i.e All levels are completely filled except last levels which has all keys as left as possible.
- Binary Heap is either a Max heap or Min Heap.
The value of each node is less than or equal to value of its parent. Thus, root contains max value.
The value of each node is greater than or equal to value of its parent. Thus, root contains min value.
Data Structure to represent a Binary Heap
There are two ways to implement Binary Heap, either using Linked List or Array. As it is a complete binary tree, using array as data structure is easier and preferred.
Binary Heap representation using Array:
- The root element will be at arr.
- arr[i/2] returns the parent node of ith node.
- arr[(2*i)+1] returns the left node of ith node.
- arr[(2*i)+2] returns the right node of ith node.
- Max Heap
- Min Heap
Application of Binary Heap
- Heap Sort: Binary Heap is used in sorting algorithm. However, Merge Sort and Quick Sort is preferred and mostly used instead of Heap Sort.
- Priority Queue: Binary Heap supports insert(), delete(). extractMax() and extractMin() operation in O(logn) time. So it is ideal to implement Priority Queue.
- Binary Heap is use to solve complex problem in programming like sort an almost sorted array, get medium of large data set and so on.
- Graph Algorithm: Priority Queue is preferred for traversal of graph algorithm like Prim’s Minimum spanning Tree and Dijkstra’s Shortest path.
Follow below examples to create Max Heap and Min Heap
- Max Heap in Java
- Min Heap in Java