Lecture 15 Objectives

At the end of today's class you should

KNOW:

That a priority queue is a data structure with the following operations:
- addElt: adds the given element to the priority queue (returns a priority queue)
- remMinElt: removes the smallest element from the priority queue (returns a priority queue)
- minElt: returns, but doesn't remove, the smallest element from the priority queue
That a heap is a binary tree with the invariant that the value in a node is less than the values of the nodes in its subtrees
That a heap provides constant-time access for the minElt() operation, and logarithmic time for the addElt() and removeMinElt() operations

BE ABLE TO:

Describe the algorithm that merges two heaps (for maxiphobic heaps)
Show the effect of the operations minElt(), removeMin(), and addElt() on a heap

Sample Exam Question:

Show the result of running the merge algorithm on the following heaps:

            3                      4
          /   \                  /   \
         6     5               17     23
                \
                 19