Examples

Heads up: although WingNotes is still useable at your current screen size, it's best viewed using a desktop browser instead!

These notes are from the MIT 6.006 Introduction to Algorithms course.


Priority Queues

A data structure with a set S of elements where:

  • each element includes a priority value that determines its place in the queue
  • the queue is ordered from highest priority to lowest
  • each element has a key
  • each element can support the following operations:
insert(S,x): insert element x into set S

max(S): return element of S with largest key

extract_max(S): return element of S with largest key and remove it from S

increase_key(S,x,k): increase the value of element x’s key to new value k (assumed to be as large as current value)

Heaps

  • Implementation of a priority queue
  • An array, visualized as a nearly complete binary tree
  • Max Heap Property: The key of a node is ≥ than the keys of its children (Min Heap defined analogously)

Heap-Sort Sorting Strategy:

  1. Build Max Heap from unordered array
  2. Find maximum element A[1];
  3. Swap elements A[n] and A[1]: now max element is at the end of the array!
  4. Discard node n from heap (by decrementing heap-size variable)
  5. New root may violate max heap property, but its children are max heaps. Run max_heapify to fix this.
  6. Go to Step 2 unless heap is empty.




Run time

  • after n iterations the Heap is empty
  • every iteration involves a swap and a max_heapify operation
  • therefore, takes O(log n) time


Use WingNotes for free

(New accounts auto-created)

Built by Brandon Le

Privacy and Terms