Implementation of priority Queue using Heap?

Answer 1

1. Now let's consider how to implement priority queues using a heap. The standard approach is to use an array (or an ArrayList), starting at position 1 (instead of 0), where each item in the array corresponds to one node in the heap:

   • The root of the heap is always in array[1].
   • Its left child is in array[2].
   • Its right child is in array[3].
   • In general, if a node is in array[k], then its left child is in array[k*2], and its right child is in array[k*2 + 1].
   • If a node is in array[k], then its parent is in array[k/2] (using integer division, so that if k is odd, then the result is truncated; e.g., 3/2 = 1).
   Here's an example, showing both the conceptual heap (the binary tree), and its array representation:

   Note that the heap's "shape" property guarantees that there are never any "holes" in the array.

   The operations that create an empty heap and return the size of the heap are quite straightforward; below we discuss the insert and removeMax operations.

   Implementing insertWhen a new value is inserted into a priority queue, we need to:
   • Add the value so that the heap still has the order and shape properties, and
   • Do it efficiently!
   The way to achieve these goals is as follows:
   1. Add the new value at the end of the array; that corresponds to adding it as a new rightmost leaf in the tree (or, if the tree was a complete binary tree, i.e., all leaves were at the same depth d, then that corresponds to adding a new leaf at depth d+1).
   2. Step 1 above ensures that the heap still has the shapeproperty; however, it may not have the order property. We can check that by comparing the new value to the value in its parent. If the parent is smaller, we swap the values, and we continue this check-and-swap procedure up the tree until we find that the order property holds, or we get to the root.
   Here's a series of pictures to illustrate inserting the value 34 into a heap: