Priority Queues and Heaps

Read Algorithms 2.4

Here is a video lecture for today's lesson.

The video contains sections on

1. Priority Queue ADT (0:27)
2. Choosing a data structure (6:15)
3. Binary heap (9:35)
4. Binary heap operations (15:25)
5. removeMin (19:26)
6. add (24:12)
7. Array-based implementation (29:32)
8. Array-based example (34:19)

The Panopto viewer has table of contents entries for these sections: https://carleton.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=b477914a-430d-41c3-b3fb-acd4017e7888

After this lesson you will be able to

1. Describe the priority queue ADT and some of its applications
2. Use the heap data structure to implement a priority queue
3. Perform operations on a heap

A priority queue is a queue-like data structure that stores elements with data and comparable priorities. You might say that the largest priority value is the most important, or that the smallest is the most important (e.g., is "priority 100" or "priority 1" the most important). This is simply a convention and the ADT functions similarly either way. For this lesson I will treat the smallest priority as the most important: "priority 1" is more important than "priority 4".

The priority queue ADT defines three primary operations:

• add: add an element to the queue
• getMin: return the most important element
• removeMin: remove and return the most important element
• isEmpty: are there elements left in the queue?

A binary min-heap (or just binary heap or just heap) is:

• Structure property: A complete binary tree
  • We previously discussed how a full tree is one with all levels filled out—the maximum number of nodes for a given height
  • A complete tree is one that that is full except for the lowest level, which must be partially filled in from left to right.
• Heap property: The priority of every node is more important than the priority of its descendents
• NOT a binary search tree

So:

• Where is the most important element? At the root
• What is the height of a heap with \(n\) elements? \(\log n\)

• Pros:
  • Non-data space: just index 0 and unused space on right
    • In conventional tree representation, an average of one edge per node (leaves have 0, interior have 1 or 2), so linear additional space required (like next/prev for linked lists)
    • Array would waste more space if tree were not complete
  • Multiplying and dividing by 2 is very fast (shift operations in hardware)
  • Last used position is just index size
• Cons:
  • Same might-be-empty or might-get-full problems we saw with stacks and queues (resize by doubling as necessary)

Pros outweigh cons: this is how people do it

1. Which of the following statements about min-heaps is true?
   1. Smaller values are on the left and larger values are on the right.
   2. The smallest value is the root.
   3. The smallest value is one of the leaves.
   4. Every value is smaller than all values at lower levels of the tree. For example, if there is a 25 at level 3, there will not be any elements with values less than 25 at levels 4 and beyond.
2. If a binary heap has 26 nodes, what is its height? If it has 73 nodes, what is the height? How do you know for sure?
3. Draw the tree for the binary min-heap that results from inserting 4, 9, 3, 7, 2, 5, 8, 6 in that order into an initially empty heap.
4. Perform 3 removals on the heap you drew in the previous problem. Show the complete state of the tree after each removal.
5. Draw the state of the array for an array-based min-heap after each of the values 3, 4, 7, 0, 2, 8, and 6 are added, in that order.
6. Draw the tree version of a min-heap being represented by the given array:

• The heap data structure is unrelated to the heap, the region of memory
• Questions?
• Form questions
• Exercise
  • Starting with MinIntHeap.java, add and test two methods
  • First is the checkHeap() method, whose purpose is to ensure the heap property is followed (as a way of debugging/ensuring the implementation is correct)
    • Note how checkHeap is called in the other methods—a "check" method like this is a great strategy for testing a data structure implementation
    • The method should check every parent-child pair
    • If a parent is greater than a child, throw new RuntimeException("HELPFUL MESSAGE GOES HERE");
      • Arrays.toString(heap) will produce a string version of the heap array
    • The provided add and removeMin methods are correct, so running the initial main method should not cause any exceptions
    • Switch to the other main method: running that should cause an exception because it uses the constructor that takes an array to use as the initial heap
    • Since this constructor does nothing to ensure the array is a valid heap, checkHeap should catch a problem
  • Second is the MinIntHeap(int[] input, int size) constructor
    • input is a binary tree represented using an array, but not one that necessarily observe the heap property
    • The constructor should heapify the array, percolating appropriately to enforce the heap property
    • This is essentialy problem 13.10 from Bailey:

      Reconsider the "heapifying" constructor discussed in Section 13.4.2. Instead of adding \(n\) values to an initially empty heap (at a cost of \(O(n \log n)\)), suppose we do the following: Consider each interior node of the heap in order of decreasing array index. Think of this interior node as the root of a potential subheap. We know that its subtrees are valid heaps. Now, just push this node down into its (near-)heap.

    • Use the checkHeap you just wrote to help you debug this constructor
    • Once you think it's working, increase the size of input to make sure
  • My solution: MinIntHeapExtended.java