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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall k (k_\mbox{min} \le 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:

Put n elements of S into P using insertItem()
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:

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

Function(s)	Unsorted Sequence	Sorted Sequence
size, isEmpty	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(1)}	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(1)}
insertItem	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(1)}	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n)}
minElement, minKey, removeMin	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n)}	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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

Turn sequence into a priority queue (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n)} )
removeMin() for all items, inserting them back into the sequence (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n^2)} )

bottleneck in Part 2

Insertion Sort

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

Turn sequence into a priority queue by inserting items into correct position (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n^2)} )
removeMin() for all items, putting them back into the sequence (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n)} since already sorted)

bottleneck in Part 1

Heaps

Implementation of priority queue with a binary tree:

Root node's key is smallest of entire tree
internal node's key is the smallest of their subtree
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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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: (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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: (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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:

Interface from InspectableBinaryTree
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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} :

Combine subtrees with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} as root
bubble-down

In general, for heaps of height Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (2^h-1) + (2^h-1) + 1 = 2^{h+1}-1}

costs Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h} (or Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h+1} ) to bubble-down