Chapter 4: Heaping it on

The following are the code listings for Chapter 4. [book.py]

• Listing 4-1. Linked list implementation of Queue data type
• Listing 4-2. Heap implementation showing enqueue() and swim() methods
• Listing 4-3. Heap implementation completed with dequeue() and sink() methods

---

Listing 4-1. Linked list implementation of Queue data type

class Node:
  def __init__(self, val):
    self.value = val
    self.next = None

class Queue:
  def __init__(self):
    self.first = None                     ❶
    self.last = None

  def is_empty(self):
    return self.first is None             ❷

  def enqueue(self, val):
    if self.first is None:                ❸
      self.first = self.last = Node(val)
    else:
      self.last.next = Node(val)          ❹
      self.last = self.last.next

  def dequeue(self):
    if self.is_empty():
      raise RuntimeError('Queue is empty')

    val = self.first.value                ❺
    self.first = self.first.next          ❻
    return val

❶ Initially, first and last are None.
❷ A Queue is empty if first is None.
❸ If Queue is empty, set first and last to newly created Node.
❹ If Queue is nonempty, add after last, and adjust last to point to newly created Node.
❺ first refers to the Node containing value to be returned.
❻ Set first to be the second Node in the list, should it exist.

Listing 4-2. Heap implementation showing enqueue() and swim() methods

class Entry:
  def __init__(self, v, p):
    self.value = v
    self.priority = p

class PQ:
  def less(self, i, j):                               ❶
    return self.storage[i].priority < self.storage[j].priority

  def swap(self, i, j):                               ❷
    self.storage[i],self.storage[j] = self.storage[j],self.storage[i]

  def __init__(self, size):                           ❸
    self.size = size
    self.storage = [None] * (size+1)
    self.N = 0

  def enqueue(self, v, p):                            ❹
    if self.N == self.size:
      raise RuntimeError ('Priority Queue is Full!')

    self.N += 1
    self.storage[self.N] = Entry(v, p)
    self.swim(self.N)

  def swim(self, child):                              ❺
    while child > 1 and self.less(child//2, child):   ❻
      self.swap(child, child//2)                      ❼
      child = child // 2                              ❽

❶ less() determines if storage[i] has lower priority than storage[j].
❷ swap() switches the locations of entries i and j.
❸ storage[1] through storage[size] will store the entries; storage[0] is unused.
❹ To enqueue a (v, p) entry, place it in the next empty location and swim it upward.
❺ swim() remakes the storage array to conform to the heap-ordered property.
❻ The parent of the entry in storage[child] is found in storage[child//2], where child//2 is the integer result of dividing child by 2.
❼ Swap entries at storage[child] and its parent storage[child//2].
❽ Continue upward by setting child to its parent location as needed.

Listing 4-3. Heap implementation completed with dequeue() and sink() methods

  def dequeue(self):
    if self.N == 0:
      raise RuntimeError ('PriorityQueue is empty!')

    max_entry = self.storage[1]                         ❶
    self.storage[1] = self.storage[self.N]              ❷
    self.storage[self.N] = None
    self.N -= 1                                         ❸
    self.sink(1)
    return max_entry.value                              ❹

  def sink(self, parent):
    while 2*parent <= self.N:                           ❺
      child = 2*parent
      if child < self.N and self.less(child, child+1):  ❻
        child += 1
      if not self.less(parent, child)                   ❼
        break
      self.swap(child, parent)                          ❽
      parent = child

❶ Save entry of highest priority on level 0.
❷ Replace entry in storage[1] with entry from bottommost level of heap and clear from storage.
❸ Reduce number of entries before invoking sink on storage[1].
❹ Return the value associated with entry of highest priority.
❺ Continue checking as long as parent has a child.
❻ Select right child if it exists and is larger than left child.
❼ If parent is not smaller than child, heap-ordered property is met.
❽ Swap if needed, and continue sinking down, using child as new parent.