Page 265 - DCAP407_DATA_STRUCTURE

Data Structure

To perform the node deletion, we have to push the largest value on the top of the heap into an array
and replace the value by the extreme left element in the tree as represented in figure 14.16.

Figure 14.16 Node Deletion

Now we obtain a tree which is not balanced. Therefore, we repeat the process of heapification to end
with the largest element in the top node of the tree. This element is now pushed again into the array,
and the extreme left bottom element replaces it. As we repeat this process, we finally obtain the sorted
array as shown in figure 14.17.

Figure 14.17: Sorted Array

The time efficiency of heapsort is O(n log n) in both the worst and average cases.

14.5 Priority Queue Using Heap

A priority queue is a queue with items having an orderable characteristic called priority. The objects
having the highest priority are always removed first from the priority queues.

A priority queue can be obtained by creating a heap. First call a function that creates an ascending heap.
After creating the heap, delete the root node and call a function to recreate the heap for the remaining
elements. This method helps in implementing an ascending priority queue. In the same way, we can
implement a descending priority queue.
The standard approach to implement priority queues using a heap is to use an array starting at position
1 (instead of 0), where each item in the array relates to one node in the heap:

1. Array[1] holds the root of the heap
2. Array[2] holds the left child
3. Array[3] holds the right child

258 LOVELY PROFESSIONAL UNIVERSITY