Lecture 24 - 03/15

Heaps and Priority Queues

Implementing a PQ using a Heap:

Representing Trees in Java

  1. Create a mapping from parent nodes to children nodes (similar to having a linked-list of nodes and pointers)
    1. Fixed-width nodes (like in BSTs)
    2. Variable-width nodes (each parent node has an array of children nodes)
    3. Sibling tree (each parent node has a pointer to a "first-born" child, whom in turn points to his next-oldest sibling, who in turn points to the next-oldest sibling, ... (essentially a linked-list of children nodes))
  2. Store keys in an array, and store parents in another array (indices between the two arrays correspond to the same node; order of nodes in the arrays has some correspondance to order of nodes in the actual tree)
  3. Cleaner approach, very nice for heaps: store keys in array; assume the tree is complete
    • The parent of a node at index k is at index k / 2
    • The left child of a node at index k is at index 2k
    • The right child of a node at index k is at index 2k+1
    • Note: can use array's size method to find index of last element in array/heap

Summary