7. Heaps And Priority Queues

Objective: In this lecture, we'll discuss the heap data structure and its C++ implementation. Topics include:

In this lecture unit, we show:

7.1 Balnaced Binary Trees

Theorem 1 Let T be a binary tree of height h. Then

Theorem 2 Let T be a nonempty binary tree, and n(i) be the number of nodes having i children, i = 0, 1, 2. Then 

    n(0) = n(2) + 1.

A regular (or full) tree is a binary tree for which each node has either both or none children.

Theorem 3 In a regular binary tree, the number of internal nodes is one less than the number of leaves.

A binary tree of height h is

Theorem 4 Let T be a completely balanced binary tree with n nodes. Then the height of T is 

    h(T) = ceiling(lg(n+1)) - 1 = floor(lg n).

Theorem 5 If the n nodes of a complete binary tree are numbered from 1 through n in breadth-first order (level-by-level from root to leaves, and at each level from left to right), then for any node with index i, we have

7.2 Heaps

7.3 Binary Heap Class (1)

template <class T>
class BinaryHeap
{
public:
   BinaryHeap() : array(11), theSize(0) {}
   BinaryHeap(const vector<T> &v);

   bool isEmpty() const { return theSize == 0; }
   const T &findMin() const;

   void insert(const T &x);
   void deleteMin();
   void deleteMin(T &minItem);
   void makeEmpty();

private:
   vector<T> array;
   int theSize;

   void buildHeap();
   void downHeap(int hole);
};

7.4 Binary Heap Class (2)

template <class T>
BinaryHeap<T>::downHeap(int hole)
{
   int child;
   T tmp = array[hole];

   for (; hole * 2 <= theSize; hole = child)
   {
      child = hole * 2;

      if (child != theSize && array[child+1] < array[child])
      {
         ++child;
      }

      if (array[child] < tmp)
      {
         array[hole] = array[child];
      }
      else
      {
         break;
      }
   }

   array[hole] = tmp;
}

template <class T>
BinaryHeap<T>::buildHeap()
{
   for (int i = theSize / 2; i > 0; --i)
      downHeap(i);
}

template <class T>
BinaryHeap<T>::BinaryHeap(const vector<T> &v)
   : array(v.size() + 1), theSize(v.size() + 1)
{
   for (int = 0; i < v.size(); ++i)
   {
      array[i+1] = v[i];
   }

   buildHeap();
}

template <class T>
const T &BinaryHeap<T>::findMin() const
{
   assert(!isEmpty());
   return array[1];
}

template <class T>
void BinaryHeap<T>::insert(const T &x)
{
   array[0] = x;  // initialize sentinel

   if (theSize + 1 == array.size())
   {
      array.resize(array.size() * 2 + 1);
   }

   // Upheap
   int hole = ++theSize;

   for (; x < array[hole / 2]; hole /= 2)
   {
      array[hole] = array[hole / 2];
   }

   array[hole] = x;
}

template <class T>
void BinaryHeap<T>::deleteMin()
{
   assert(!isEmpty())
   array[1] = array[theSize--];
   downHeap(1);
}

template <class T>
void BinaryHeap<T>::deleteMin(T &minItem)
{
   minItem = findMin();
   array[1] = array[theSize--];
   downHeap(1);
}

7.5 Heap Sort

Algorithm 1 (Heapsort) Sort an array.

7.6 Heap Sort Implementation

heapSort(vector<T> &a)
{
   // Build heap
   for (int i = a.size() / 2; i >= 0; --i)
   {
      downHeap(a, i, a.length());
   }

   // deleteMax
   for (int j = a.size() - 1; j > 0;--j)
   {
      swap(a[0], a[j]);
      downHeap(a, 0, j);
   }
}

where downHeap can be written very similarly to the one for the BinaryHeap class.

7.7 Heap Sort Efficiency

Theorem 6 Let v be a vector, and n = v.size(). Then

Proof:

Let the tree have m levels. A key k in a node at level i could be exchanged with children along any downward path at most m - i times before coming to rest. Since there are at most 2^i nodes on level i of the tree, we have 


               m-1
         E1 <= SUM (2^i * (m-i))
               i=0
                m
             = SUM (j * 2^(m-j))
               j=1
                      m
             = 2^m * SUM (j / 2^j)
                     j=1
            <  2^m * 2
            <= 2n.


                m
         E2 <= SUM (i+1) * 2^i + E1
               i=0
               m+1
	     = SUM j * 2^(j-1) + E1
               j=1
             = 2^(m+1) * m + 1 + E1
             = O(n lg(n)).

7.8 Priority Queues

A priority queue is set of items on which only two operations are performed:

Different implementations: 

  Implementation                     Time Complexity 
  =================================  =================
  (1) Unsorted array or linked list  Insert: O(1)
                                     Remove: O(n)
  (2) Sorted array or linked list    Insert: O(n)
                                     Remove: O(1)
  (3) Maximum Heap                   Insert: O(lg(n))
                                     Remove: O(lg(n))