Advanced Programming I Lecture Notes

15 March 2007 • Heaps and Priority Queues

#include <algorithm>  // for std::swap().

template <typename T>
static void
bubble_up(T a[], unsigned i) {

  while (i > 0) {
    const unsigned p = i/2;
    if (a[p] ≥ a[i])
      break;
    std::swap(a[p], a[i]);
    }
  }


template <typename T>
static void
bubble_down(T heap[], unsigned n) {

  unsigned i = 0;

  while (true) {
    unsigned c = 2*i + 1;
    const unsigned c1 = 2*(i + 1);

    if (c ≥ n)
      break;
    if ((c1 < n) and (heap[c] < heap[c1]))
      c = c1;

    if (heap[i] ≥ heap[c])
      break;

    std::swap(heap[i], heap[c]);
    i = c;
    }
  }


template <typename T>
void
heap_sort(T a[], unsigned n) {
  for (unsigned i = 1; i < n; i++)
    bubble_up(a, i);

  for (unsigned i = n - 1; i > 0; i--) {
    std::swap(a[0], a[i]);
    bubble_down(a, i);
  }

This page last modified on 24 January 2006.