Data Structure and Algorithm Design

Sections

• Heap

• Priority Queue

Heap Data Structure

Outline

• Definitions

• Structures

• Behaviors

• Visualization

• Time Complexity

Overview

• Definition: A complete binary tree in which parent node is always less/greater (min/max heap) or equal (if allow overlapped values) than all elements in its subtrees.

• Two type: min and max heap

• Applications

  • Heap sort

  • Priority queue

Structures

• Logically a complete binary tree

• Physically a partially filled array

  • find parent/children by arithmetic calculation of indices

    • given the node \(i\)

    • the index of the parent node is \((i-1)/2\)

    • the indices of the children nodes are left: \(i*2+1\) and right: \(i*2+2\)

Behaviors

• Heapify: make an array of random numbers into a heap

• Insert: insert a new element into a heap

  • insert at the end of the array

  • percolate up

• Delete: delete an element from a heap

  • use the last element to replace the root

  • percolate down

• Percolate up: move an element up to its proper position

• Percolate down: move an element down to its proper position

Visualization

• Our Binary Heap Visualizer shows the tree and array views while stepping through heap operations.

• http://www.cs.usfca.edu/~galles/visualization/Heap.html

• https://visualgo.net/en/heap

Time Complexity

• Create a heap

  • From an array (heapify) \(\Theta(n)\)

  • Insert one by one \(\Theta(n\log n)\)

• Insert \(\Theta(\log n)\)

• Delete \(\Theta(\log n)\)

• Percolate up \(\Theta(\log n)\)

• Percolate down \(\Theta(\log n)\)

Heap Sort

• Heap sort is a comparison based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for remaining element.

• Characteristics

  • Comparison based (general purpose)

  • Iterative

  • In-place

  • Efficient

  • Unstable - relative order of equal elements is not preserved

Algorithm Details

1. Heapify the array to build a heap

2. Removing the root node repeatedly from a heap

   • move root to the sorted region by swapping it with the last leaf

   • percolate the root down

• Related data-structure demo: our Binary Heap Visualizer steps through heap operations and shows the array/tree representation.

• Heapsort visualization: https://www.cs.usfca.edu/~galles/visualization/HeapSort.html

Pseudo Code

function heapSort(arr):
  n = length(arr)

  # Heapify the array
  for i from n/2-1 down to 0:
    percolateDown(arr, n, i)

  # Extract elements from the heap one by one
  for i from n - 1 down to 1:
    # Swap the root (maximum element) with the last element
    swap(arr[0], arr[i])
    percolateDown(arr, i, 0)

function percolateDown(arr, n, i):
  largest := i
  left := 2 * i + 1
  right := 2 * i + 2

  # Compare with left child
  if left <= n and arr[left] > arr[largest]:
    largest := left

  # Compare with right child
  if right <= n and arr[right] > arr[largest]:
    largest := right

  # If the largest element is not the root, swap them
  if largest != i:
    swap(arr[i], arr[largest])

    # Recursively percolate down the affected sub-tree
    percolateDown(arr, n, largest)

Complexity

• Time \(\Theta(n \log n)\)

• Space \(\Theta(1)\) as an in-place algorithm

Priority Queue Abstract Data Type

Compare priority-queue operations in our ADT Explorer and inspect the underlying heap in our Binary Heap Visualizer.

• Overview

• Behaviors

Overview

• A priority queue ADT is a container of elements that guarantees that the element with the highest priority is the first element to be obtained and removed from the container.

• It is not really a queue because it is not FIFO!

• Characteristics

  • Homogeneous

  • Access order is highest/lowest rank first

  • Finite

  • Dynamic size

• Applications

  • Many greedy algorithms

  • Event-driven simulation

  • Dijstra’s shortest path algorithm

Behaviors

• enqueue: Add an element to the priority queue.

• dequeue: Remove and return the value of the element with the highest/lowest rank from the priority queue.

• peek: Return the element to be removed from the queue.

• isEmpty: Return true if the stack is empty, false otherwise.

• size (optional): Return the number of elements in the container.

C++ Implementation of Priority Queue ADT

See our Binary Heap Visualizer for the tree and array representation used by one common implementation.

• Use C++ STL container std::priority_queue

• Make from scratch as templates

• Example public interface:

  template <typename T>
  class PriorityQueue {
   private:
    ///...
   public:
    void enqueue(const T& value);
    T dequeue();
    T peek() const;
    bool isEmpty() const;
  };

Data Structures

• Heap

• Sorted array or linked list

  • enqueue: perform a sorted insert (part of the insertion sort algorithm)

  • dequeue: remove the first/last element