Please enable JavaScript.
Coggle requires JavaScript to display documents.
Heaps and Heapsort - Coggle Diagram
Heaps and Heapsort
Notion of the Heap
-
It must satisfy the shape property (essentially complete binary tree) and the parental dominance property (parent's key is greater than or equal to the keys in its children).
The key values follow a top-down order in a heap, with decreasing values along any path from the root to a leaf.
Properties
-
-
-
A heap can be represented as an array, where elements are stored in a specific order to maintain the heap properties.
Parental keys are in the first half of the array, and leaf keys are in the second half.
The relationship between parent and child nodes in the array representation is defined for efficient heap operations.
Definition
-
-
Operations on priority queues include finding the highest priority item, deleting it, and adding new items.
Heapsort
Stages
- Construct a heap for a given array
After the deletion operations, the array is sorted in increasing order due to the way elements are removed under the array implementation of heaps.
- Apply root-deletion operation n-1 times to the remaining heap.
Time Efficiency
-
-
In both worst and avarege cases, it is similar to mergesort but worst than quicksort
Applications
Priority queues are essential in scheduling job executions and traffic management.
They are used in algorithms like Prim's algorithm, Dijkstra's algorithm, Huffman encoding, and branch-and-bound applications.