CS212 Handouts
Mutable Data Structures
  • Stacks and Queues
  • Priority Queues
  • List Implementation of Priority Queues
  • Heaps
  • Vectors
  • Heap Implementation of Priority Queues

    • Stacks and Queues

    The abstract data structures stack and queue are not difficult to implement in such a way that all the basic operations can be performed in constant time. Scheme lists are good for implementing a stack, because the insert, delete, and top operations can be implemented easily using cons, tail, and head respectively. For a queue, a naive list implementation would require that either the insert! or the delete! and head operations be linear instead of constant time. This is because elements are added at one end of the list and removed from the other. A simple solution is to build a structure with pointers to both ends of a list, and to mutate this structure when elements are added and removed from the queue. This enables us to provide constant time queue operations as well as constant time stack operations. 
    (defgeneric (empty? q))
(defgeneric (insert! x q))
(defgeneric (head q))
(defmethod (head q) (first q)) ;so that head will still work for lists

(defclass <queue> ()
  (front :type <list> :initarg :front :accessor front :initvalue empty)
  (back :type <list> :initarg :back :accessor back :initvalue empty))

(defmethod (empty? (q <queue>))
  (null? (front q)))

(define (make-queue)
  (make <queue>))

(defmethod (head (q <queue>))
  (if (empty? q)
      (error "queue is empty")
      (head (front q))))

(defmethod (insert! x (q <queue>))
  (let ((new (list x)))
    (if (empty? q)
        (set! (front q) new)
        (set! (tail (back q)) new))
    (set! (back q) new))
  q))

(define (delete! (q <queue>))
  (if (empty? q)
      (error "queue is empty")
      (set! (front q) (tail (front q))))
  q))

    Priority Queues

    Like stacks and queues, a priority queue is another structure for inserting and removing data in a particular order. The priority queue differs from either of these other structures in that the order is defined by the data itself, rather than by the order in which the data is inserted. Each element in a priority queue has a priority associated with it. The most important (or "first'') element in a priority queue is generally defined to be the one with the smallest priority.

    A priority queue implements the operations insert! and extract-min!, where the minimum is the most important element. We will consider two different methods of implementing priority queues: one using a list and the other using a structure called a heap. Both of these implementations will make use of mutation operations which modify the data structures destructively. The heap implementation also makes use of vectors.

    We define entries in a priority queue as a class consisting of a priority and value: 

    (defclass <entry> ()
  (key :type <number> :initarg :key :accessor key)
  (value :type <top> :initarg :value :accessor value))

(define (make-entry (k <number>) v)
  (make <entry> :key k :value v))
    The insert! operation for a priority queue adds a given entry (key and value) to a priority queue. The extract-min! operation removes the entry with the smallest key from the priority queue (the most important element), and returns it as a value.

    List Implementation of Priority Queues

    First we will consider a fairly straightforward implementation of this data structure using a list to store the elements in the priority queue. There are two options:

    By maintaining the list with smaller numbered entries (higher priority) first, the extract-minimum operation is simple, but the insertion operation is complicated. Maintaining the list as unordered entries makes extract-minimum complicated but insertion simple. We somewhat arbitrarily choose the first option, and maintain the list in order, with smaller numbered entries at the front.

    We represent a priority queue as a data structure containing a list of elements: 

    (defclass <prioq> (<collection>))

(defclass <lprioq> (<prioq>)
  (data :type <list> :initarg :data :accessor data :initvalue empty))

(define (make-lprioq)
  (make <lprioq>))

(defmethod (empty? (pq <lprioq>))
  (null? (data pq)))
    An element is inserted into a priority queue by iterating down the list until the proper place is found, at which point the new element is spliced into the list. The "proper place'' is where the next element in the list has higher priority than the element that we are inserting. The case of an empty structure, or a structure where the new entry goes at the front (has the smallest priority number) are handled specially. 
    (add-method (insert! (entry <entry>) (prioq <lprioq>))
  ;; In the general case iterate until the location to insert the entry
  ;; is found.  This is either when the next entry has greater priority,
  ;; or there is no next entry.  Note: it is the CURRENT entry's tail
  ;; that is modified when the NEXT entry has greater priority.
  (letrec
      ((helper (lambda ((rest <list>))
         (cond ((null? (tail rest))
                (set! (tail rest) (list entry)))
               ((> (key (second rest)) (key entry))
                (set! (tail rest) (pair entry (tail rest))))
               (else (helper (tail rest))))))
    ;; Initial cases: if there is no data then entry is the only data,
    ;; if new entry is less than the first entry then just add it to
    ;; the front, else the general case of between CURRENT and NEXT.
    (cond ((null? (data prioq)) (set! (data prioq) (list entry)))
          ((> (key (head (data prioq))) (key entry))
           (set! (data prioq) (pair entry (data prioq))))
          (else (helper (data prioq)))))))
    The extract-min! operation removes and returns the smallest priority ("most important'') element: 
    (defgeneric (extract-min! q))

(defmethod (extract-min! (prioq <lprioq>))
  (if (null? (data prioq))
      (error "queue is empty")
      (let ((v (head (data prioq))))
        (set! (data prioq) (tail (data prioq)))
        v))))

    The insertion operation is linear time, because in the worst case every element in the structure is considered in the process of adding a new element. The extraction operation, on the other hand, is constant time. If we used an unordered list, the opposite would be true: insertion would be constant time and extraction would be linear time.

    We can use a priority queue to sort a list of n numbers. Just insert each element into the priority queue, then do repeated extract-minimum operations. The time complexity is O(n2) for the n insertions (n operations of O(n) time each), which dominates the O(n) time for the n extractions (n operations of O(1) time each). 

    (define (prioq-sort (elts <list>))
  (let ((prioq (make-lprioq)))
    (bind-methods
        ((insert-em! (lambda (x)
           (insert! (make-entry x x) prioq)))
         (extract (lambda ()
           (if (empty? prioq)
               empty
               (pair (value (extract-min! prioq)) (extract))))))
      (map insert-em! elts)
      (extract)))))

    Heaps

    We can implement priority queues more efficiently using a structure called a heap, with the result that insertion and extraction are both O(log n) time operations.

    A heap is a tree in which each node stores one data item. A heap must satisfy the heap ordering property: the priority value of a node is less than or equal to the priority values of both its children. This property implies that the element of minimum value is at the root. This can be proved formally by induction.

    Vectors

    We will implement heaps as vectors. In Scheme a vector is a sequence like a list, except each element is directly accessible in constant time using an address or index. The contract of the vector operations is that 
    (vector-set! vec i val)
(vector-ref vec i) ==> val
    for any value val and for 0 <= i < (vector-length vec). Furthermore, 
    (vector-length (make-vector n)) ==> n
    An alternative form of the constructor is (vector x0 ... xn-1), which evaluates x0 ... xn-1 and creates a vector of length n with those values. The contract is 
    (vector-ref (vector x1 ... xn-1) i) ==> xi
    for 0 <= i < n. A heap can be represented using a vector. A vector of n+1 elements is used to store a heap with a maximum of n entries. The elements of the heap are stored in contiguous vector positions beginning at index 1. The index of the last element of the vector that is currently in use is stored at index 0. This is the same as the number of elements in the heap. For each index i, the children of the node stored at location i in the vector, if they exist, are stored at locations 2i and 2i+1. The root is stored at location 1.

    Given this representation, the heap ordering property translates to: v[i] <= v[2i] and v[i] <= v[2i+1], provided the children of the node at i exist; this can be tested by comparing 2i and 2i+1 to v[0].

    Heap Implementation of Priority Queues

    We define a priority queue as a data structure with containing a vector, where initially the first element of the vector is zero, indicating an empty heap. 
    (defclass <vprioq> (<prioq>)
  (data :type <vector> :initarg data :accessor data))

(define (make-prioq size)
  (let ((v (n-vector (1+ size))))
    (vector-set! v 0 0)
    (make <vprioq> :data v))))

(defmethod (empty? (prioq <vprioq>))
  (zero? (vector-ref (data prioq) 0)))
    An element is inserted into priority queue by placing it at a leaf node (in last position of the vector) and then percolating it upward by switching with its parent until it reaches the point where the parent is smaller than the element. This operation requires only O(log n) time, because the percolation goes up from a leaf to the root in a binary tree of n elements, doing a constant amount of work at each node. In the vector implementation, the index is halved on each iteration.
    (defmethod (insert! (entry <entry>) (prioq <vprioq>))
  (let ((pri (key entry))
        (heap (data prioq)))
  ;; Keep walking up the tree (by dividing the vector index in half)
  ;; swapping values until the parent is smaller than the child.
    (letrec
      ((push-up (lambda (i)
         (cond ((and (> i 1)
                     (< (key (vector-ref heap i))
                        (key (vector-ref heap (/ i 2)))))
                (let ((temp (vector-ref heap i)))
                  (vector-set! heap  i (index heap (/ i 2)))
                  (vector-set! heap (/ i 2) temp)
                  (push-up (/ i 2))))))))
      ;; Add the element at the end and increment the last-used counter
      (cond ((= (index heap 0) (1- (length heap)))
             (error "Priority queue is full"))
            (else
             (vector-set! heap 0 (inc (index heap 0)))
             (vector-set! heap (index heap 0) entry)
             (push-up (vector-ref heap 0)))))))
    The minimum element is guaranteed to be at the root of the tree (in the first position of the vector) by the heap order property. Thus the extract-minimum operation just removes and returns that element. The structure is updated by copying a leaf element (from the last occupied cell of the vector) to the root (the first entry of the vector) and propagating the value down the tree until it is greater than its parent. Similarly to the insert operation, this requires only O(log n) time, because the value is propagated down to a leaf node considering only two possible nodes at each level (from the viewpoint of the array the index is doubled on each iteration). 
    (defmethod (extract-min! (prioq <vprioq>))
  (let ((heap (data prioq)))
  ;; The following functions work on broken heaps,
  ;; in which the element i (initially the root element)
  ;; might be out of place.  
  ;; Get value at k if it exists, else false
  (letrec
      ((safe-ref (lambda ((vec <vector>) (k <integer>))
         (if (<= k (index vec 0)) (index vec k) #f)))
      ;; Starting at node i, determine which of i and its two children
      ;; (at 2i and 2i+1) has the smallest priority value.
      (smallest-priority (lambda ((i <integer>))
         (let ((pi (key (vector-ref heap i)))
               (e2i (safe-ref heap (* 2 i)))
               (e2i+1 (safe-ref heap (+ 1 (* 2 i))))
               (p2i (and e2i (key e2i)))
               (p2i+1 (and e2i+1 (key e2i+1))))
           (cond ((and p2i (or (not p2i+1) (<= p2i p2i+1)) (< p2i pi))
                  (* 2 i))
                 ((and p2i+1 (or (not p2i) (<= p2i+1 p2i)) (< p2i+1 pi)) 
                  (+ 1 (* 2 i)))
                 (else i)))))
      ;; If the current node is larger than either of its children,
      ;; interchange it with the smaller of the children, and iterate
      ;; again starting at that child.
      (push-down (lambda ((i <integer>))
        (let ((smallest (smallest-priority i)))
          (cond ((not (= smallest i))
                 (let ((temp (vector-ref heap smallest)))
                   (vector-set! heap smallest (index heap i))
                   (vector-set! heap i temp))
                 (push-down smallest)))))))
    ;; Save the min element (first element of vector), move a leaf
    ;; (last element of vector) to the min location and start loop
    ;; to push that value down the tree.
   (cond ((zero? (vector-ref heap 0))
          (error "Cannot extract from empty priority queue"))
         (else
          (let ((min (vector-ref heap 1)))
            (vector-set! heap 1 (vector-ref heap (vector-ref heap 0)))
            (vector-set! heap 0 (1- (vector-ref heap 0)))
            (push-down 1)
            min)))))))
    Now if we sort a list of numbers using this new priority queue implementation, the sorting method has worst case O(n log n) time complexity. An O(log n) insertion operation is performed for each of the n elements, and then an O(log n) extract-min! operation is performed for each element.

    We can use the same code for sorting as given above, since we made sure it was generic.


    Last Modified: 3/23/99 by Brandon Bray