Binary Heap
A binary heap is a complete binary tree which satisfies the heap ordering property.
A Binary Heap is a Binary Tree with two properties:
1) It is a complete tree (All levels are completely filled except possibly the last level and the last level has all keys as left as possible). This property of Binary Heap makes them suitable to be stored in an array.
2) A Binary Heap is either Min Heap or Max Heap.
In a Min Binary Heap, the min-heap property: the value of each node is greater than or equal to the value of its parent, with the minimum-value element at the root. The same property must be recursively true for all nodes in Binary Tree. Max Binary Heap is similar to Min Heap.
Examples of Min Heap:
10 10
/ \ / \
20 100 15 30
/ / \ / \
30 40 50 100 40
Applications of Heap Data Structure
1. Heap Data Structure is generally taught with Heapsort. Heapsort algorithm has limited uses as Quicksort is better in practice.
2. Priority Queues: Priority queues can be efficiently implemented using Binary Heap because it supports insert(), delete() and extractmax(), decreaseKey() operations in O(logn) time.
3. Binomial Heap and Fibonacci Heap are variations of Binary Heap. These variations perform union also in O(logn) time which is a O(n) operation in Binary Heap.
4. Graph Algorithms: The priority queues are especially used in Graph Algorithms like Dijkstra’s Shortest Path and Prim’s Minimum Spanning Tree.
Many problems can be efficiently solved using Heaps. See following for example.
Few more applications are:
a) K’th Largest Element in an array.
b) Sort an almost sorted array.
c) Merge K Sorted Arrays.
References:
No comments:
Post a Comment