CSCE 221 Chapter 7

« previous | Thursday, February 10, 2010 | next »

Note: I was absent for this class to present at the Teaching With Technology Conference with Dr. Philip Yasskin of the Department of Mathematics.

Priority Queue

key

an object that is "assigned" to an element for identifying/ranking/comparing that element against/among other elements.

not necessarily unique

EX: price, length, weight, speed, number in a wait line at the DPS.

Key Comparison: ≤

• Never contradicts itself (duh?)
• total order relation properties:
  • Reflexive: $k\leq k$
  • Antisymmetric: $((k_{1}\leq k_{2})\wedge (k_{2}\leq k_{1}))\rightarrow k_{1}=k_{2}$
  • Transitive: $((k_{1}\leq k_{2})\wedge (k_{2}\leq k_{3}))\rightarrow k_{1}\leq k_{3}$

makes finding smallest key an easy operation:

$\forall k(k_{\mbox{min}}\leq k)$

Comparator

A function object used to compare objects (not necessarily just numbers)

• Returns 0 if equal
• Returns -1 if less than
• Returns +1 if greater than

Functions

Given a priority queue P:

Function	Description
int size()	return the number of elements in P
bool isEmpty()	test whether P is empty
void insertItem(Key k, Object e)	insert an element e assigned with key k into P
Object& minElement()	returns a reference to element of P with smallest key (throws EmptyQueueException if empty)
const Key& minKey()	returns a constant reference (immutable for ADT integrity reasons) to smallest key of P (throws EmptyQueueException if empty)
void removeMin()	remove element of P with smallest key (throws EmptyQueueException if empty)

Application: Sorting

Given a collection S of size n randomly arranged elements, we can use the following PriorityQueueSort function to sort it using a priority queue P:

1. Put n elements of S into P using insertItem()
2. Extract elements from P back into S in ascending order using minElement() and removeMin().

void sort(Sequence& s) {
  PriorityQueue p;
  while (!s.isEmpty()) {
    e = s.removeFirst();
    p.insertItem(e,e);
  }
  while (!p.isEmpty()) {
    e = p.minElement();
    p.removeMin();
    s.insertLast(e);
  }
}

Implementation

2 ways:

1. Unsorted sequence (push items onto end regardless of key value)
2. Sorted sequence (insert based on order)

Function(s)	Unsorted Sequence	Sorted Sequence
size, isEmpty	$O(1)$	$O(1)$
insertItem	$O(1)$	$O(n)$
minElement, minKey, removeMin	$O(n)$	$O(1)$

Sample of Sorted Sequence Implementation:

template<typename Key, typename Element, typename Comp> class SortedSeqPriorityQueue {

// type declarations
protected:
  typedef Item<Key, Element> Item;       // (key, element) pair
  typedef NodeSequence<Item> Sequence;   // sequence of items

public:
  typedef Sequence::Position Position;   // position type for sequence

// local utilities and members
protected:
  const Key& key(const Position& p) const {
    return p.element().key();
  }

  Element& element(const Position& p) {
    Position t = p;
    return t.element().element();
  }

private:
  Sequence s;
  Comp comparator;                           // comparator class (returns 1 if >, 0 if =, -1 if <)

public:
  SortedSeqPrimaryQueue() : S(), comparator() {}
  int size() const { return S.size(); }
  bool isEmpty() const { return S.isEmpty(); }

  void insertItem(const Key& k, const Element& e {
    if (S.isEmpty()) {
      S.insertFirst(Item(k,e));              // if empty, insert first
    } else if (comparator(k, key(S.last())) > 0) {
      S.insertAfter(S.last(), Item(k,e));    // insert at end if greater than last
    } else {
      Position current = S.first();
      while (comparator(k, key(current)) > 0)
        current = S.after(current);
      S.insertBefore(current, Item(k,e));    // insert before the first key larger than this one
    }
  }

  Element& minElement() throw(EmptyContainerException) {
    if (S.isEmpty()) throw EmptyContainerException("empty queue");
    return element(S.first());
  }

  const Key& minKey() const throw(EmptyContainerException) {
    if (S.isEmpty()) throw EmptyContainerException("empty queue");
    return S.first());
  }

  void removeMin() throw(EmptyContainerException) {
    if (S.isEmpty()) throw EmptyContainerException("empty queue");
    S.remove(S.first());
  }

};

Selection Sort

1. Turn sequence into a priority queue ($O(n)$)
2. removeMin() for all items, inserting them back into the sequence ($O(n^{2})$)

bottleneck in Part 2

Insertion Sort

similar to Selection sort, but orders elements when inserting into Priority Queue

1. Turn sequence into a priority queue by inserting items into correct position ($O(n^{2})$)
2. removeMin() for all items, putting them back into the sequence ($O(n)$ since already sorted)

bottleneck in Part 1

Heaps

Implementation of priority queue with a binary tree:

1. Root node's key is smallest of entire tree
2. internal node's key is the smallest of their subtree
3. always a balanced, complete (saturated) binary tree

Example:

              04
      05              06
  15      09      07      20
16  25  14  12  11  08

Vector Representation

• Index starts as 1, not 0
• Always has $2n+1$ elements (to store empty "place-holder external nodes" by book's convention) why?
• Recall algorithms for finding parents/children

Insertion:

Always insert at next position of row (to keep binary tree complete). That is, next insertion position on tree above would be below 20.

Sometimes, insertion would break our heap-order—up-heap bubbling to fix: ($O(\log {n})$)

• If inserted node is less than its parent, swap with parent
• If now-swapped node is less than its new parent, swap again
• Repeat as necessary up the tree

Removal

Because heap is a glorified priority queue, removing smallest element means removing the root node.

Tree has to be re-balanced—down-heap bubbling to fix: ($O(\log {n})$)

• Remove root node
• Replace root node with node most recently inserted (last node)
• If smaller of two children is smaller than the new root node, swap
• If smaller of two new children is smaller than the swapped node (what was the root), swap again
• repeat as necessary down the tree

Sample C++ Implementation

Two abstract objects:

1. Interface from InspectableBinaryTree
2. PositionalContainer provides replaceElement() and swapElements()

template<class Object> class HeapTree : public InspectableBinaryTree, PositionalContainer {
public:
  Position add(const Object& elem);
  Object remove();
};

template<typename Key, typename Element, typename Comp> class HeapPriorityQueue {
protected:
  typedef Item<Key, Element> Item;
  typedef VectorHeapTree<Item> HeapTree;
  typedef HeapTree::Position Position;

  const Key& key(const Position& p) const {
    return p.element().key();
  }

  Element& element(const Position& p) {
    return p.element().element();
  }

private:
  HeapTree T;
  Comp comparator;

public:
  HeapPriorityQueue(int cap = 100) : T(cap), comparator() {}
  int size() const { return (T.size()-1)/2; }
  bool isEmpty() const { return size() == 0; }
  void insertItem(const Key&, const Element&);
  Element& minElement() throw(EmptyContainerException);
  const Key& minKey() const throw(EmptyContainerException);
  void removeMin() throw(EmptyContainerException);
};

template<typename Key, typename Element, typename Comp>
void HeapPriorityQueue<Key, Element, Comp>::insertItem(const Key& k, const Element& e) {
  Position z = T.add(Item(k, e));
  Position u;
  while (!T.isRoot(z)) {
    u = T.parent(z);
    if (comparator(key(u), key(z)) <= 0) break;
    T.swapElements(u, z);
    z = u;
  }
}

template<typename Key, typename Element, typename Comp>
Element& HeapPriorityQueue<Key, Element, Comp>::minElement() throw(EmptyContainerException) {
  if (isEmpty()) throw EmptyContainerException("Empty heap");
  return element(T.root());
}

template<typename Key, typename Element, typename Comp>
const Key& HeapPriorityQueue<Key, Element, Comp>::minKey() const throw(EmptyContainerException) {
  if (isEmpty()) throw EmptyContainerException("Empty heap");
  return key(T.root());
}

template<typename Key, typename Element, typename Comp>
void HeapPriorityQueue<Key, Element, Comp>::removeMin() throw(EmptyContainerException) {
  if (isEmpty()) throw EmptyContainerException("Empty heap");
  if (size() == 1) {
    T.remove();
  } else {
    T.replaceElement(T.root(), T.remove());
    Position r = T.root();
    Position s;
    while (T.isInternal(T.leftChild(r))) {
      s = T.rightChild(r);
      if (T.isExternal(T.rightChild(r)) || comparator(key(T.leftCHild(r)), key(T.rightChild(r))) <= 0)
        s = T.leftChild(r);
      if (comparator(key(s), key(r)) < 0) {
        T.swapElements(r, s);
        r = s
      } else {
        break;
      }
    }
  }
}

Tuesday, February 15, 2011

Bottom-up Construction

Fundamental Problem: Merge 2 trees given a key for a new root $k$:

1. Combine subtrees with $k$ as root
2. bubble-down

In general, for heaps of height $h$

$(2^{h}-1)+(2^{h}-1)+1=2^{h+1}-1$

costs $h$ (or $h+1$) to bubble-down

Locators

Similar to Positions in a Linked List:

Access to nodes, but not parents or children

• key()
• element()
• Position/rank in underlying tree structure

Unlike positions, locators:

• tracks items instead of representing "places" in the structure
• not related to other locators whereas positions have a next/previous (but no public access)