Heaps are regular binary trees with two special characteristics. (i) Complete Tree (ii) Order Property Heaps must be Complete Binary Trees. With order property it means that every node must have more(less) or equal key values than its child nodes. Heap is a special data structures that are useful for specific use-cases such as sorting and implementing priority queues.
Applications of Heap
- To implement Priority Queues– priority queues are used in Graph algorithms (like Prim’s Algorithm and Dijkstra’s algorithm)
- To sort given sequence using Heap Sort
- To maintain Order statistics– can be used to efficiently find the kth smallest (or largest) element in an array.
Lets develop good understanding of HEAP and its properties thorugh the Video Lectures
[Click the following links to watch the video]
- Heap – Introduction
- MaxHeapify BuildMax ExtractMax Procedures– Illustrative Example
- ANALYSIS – Build-Max-Heap/Max-Heapify/Extract-Max-Heap Algorithms
You are invited to raise queries by writing your question in the box given below
Expertvision 