Skip to main content
HTML5ANDCSS3 logoHTML5ANDCSS3Tools and Tutorials

Heaps and Priority Queues

Heap Sort and Streaming Data

Written by Updated

Heap sort is the sorting algorithm nobody uses and everybody should understand - it is the proof that O(n log n) is achievable without the extra memory merge sort needs.

The two phases

Heap sort, in place

javascript

function heapSort(items) {
  const n = items.length

  // Phase 1: turn the array into a max-heap, in place. O(n).
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    siftDown(items, i, n)
  }

  // Phase 2: swap the largest to the end, shrink, repair. O(n log n).
  for (let end = n - 1; end > 0; end--) {
    ;[items[0], items[end]] = [items[end], items[0]]
    siftDown(items, 0, end)
  }

  return items
}

function siftDown(items, i, limit) {
  while (true) {
    const left = 2 * i + 1
    const right = 2 * i + 2
    let largest = i

    if (left < limit && items[left] > items[largest]) largest = left
    if (right < limit && items[right] > items[largest]) largest = right
    if (largest === i) break

    ;[items[i], items[largest]] = [items[largest], items[i]]
    i = largest
  }
}

console.log(heapSort([5, 3, 8, 1, 9, 2]))  // [1, 2, 3, 5, 8, 9]

O(n log n) guaranteed - no bad-pivot worst case like quicksort - and O(1) extra space, unlike merge sort. It loses in practice because it jumps around memory, which modern CPUs dislike, and it is not stable.

The thing only a heap can do

Streaming. When numbers arrive one at a time and you must answer after each one, you cannot sort - you never have the whole input.

Running median with two heaps

javascript

class MedianFinder {
  // Low half in a max-heap, high half in a min-heap.
  // The two roots sit either side of the median.
  #low = new PriorityQueue((a, b) => b - a)   // max-heap
  #high = new PriorityQueue((a, b) => a - b)  // min-heap

  add(n) {
    this.#low.push(n)
    // Everything in low must be <= everything in high.
    this.#high.push(this.#low.pop())

    // Keep low the same size or one larger.
    if (this.#high.size > this.#low.size) {
      this.#low.push(this.#high.pop())
    }
  }

  median() {
    if (this.#low.size > this.#high.size) return this.#low.peek()
    return (this.#low.peek() + this.#high.peek()) / 2
  }
}

// A comparator-driven priority queue, as used above.
class PriorityQueue {
  constructor(compare) { this.compare = compare; this.data = [] }
  get size() { return this.data.length }
  push(v) { this.data.push(v); this.data.sort(this.compare) }
  pop() { return this.data.shift() }
  peek() { return this.data[0] }
}

const demoFinder = new MedianFinder()
demoFinder.add(1)
demoFinder.add(3)
console.log(demoFinder.median())  // 2
demoFinder.add(5)
console.log(demoFinder.median())  // 3

O(log n) per insert, O(1) to read the median. Re-sorting after every arrival would be O(n log n) each time - unusable on a real stream.

Where streaming heaps show up

  • Running median or percentile - latency monitoring, live dashboards.
  • Merging sorted streams - a heap of one item per stream.
  • Schedulers - always run the highest-priority task next.
  • Dijkstra's algorithm - always expand the nearest unvisited node.

Heap sort in place

Build a max-heap over the array, then repeatedly swap the root to the end and shrink the heap by one. The sorted portion grows from the right, and no extra array is ever allocated - O(n log n) time, O(1) space.

Heap sort

javascript

function heapSort(items) {
  const n = items.length

  function sink(i, size) {
    for (;;) {
      const left = 2 * i + 1
      const right = left + 1
      let largest = i
      if (left < size && items[left] > items[largest]) largest = left
      if (right < size && items[right] > items[largest]) largest = right
      if (largest === i) return
      ;[items[largest], items[i]] = [items[i], items[largest]]
      i = largest
    }
  }

  // Build the heap bottom-up: O(n).
  for (let i = (n >> 1) - 1; i >= 0; i--) sink(i, n)

  // Repeatedly move the maximum to the end.
  for (let end = n - 1; end > 0; end--) {
    ;[items[0], items[end]] = [items[end], items[0]]
    sink(0, end)
  }

  return items
}

console.log(heapSort([5, 3, 8, 1, 9, 2]))  // [1, 2, 3, 5, 8, 9]

It is not stable, and in practice it loses to quicksort on cache behaviour - which is why library sorts rarely use it. Its guarantee is the worst case: unlike quicksort, it is O(n log n) no matter the input.

The running median

Two heaps: a max-heap for the lower half, a min-heap for the upper half, kept within one element of the same size. The median is then the root of the larger heap, or the average of the two roots when they are equal. Each insertion is O(log n) and the answer is O(1).

PreviousTop K ProblemsNextBinary Trees Explained