A binary heap is a complete binary tree that maintains the heap property: every parent is either less than or equal to its children (min-heap), or greater than or equal to its children (max-heap).
Binary heaps are commonly used to implement priority queues (an abstract data type that finds its highest-priority item in time), providing efficient access to and removal of the highest-priority element, as well as efficient insertion.
One cool thing about a binary heap is that it can be represented using an array.
Some fundamentals about the binary heap:
- A binary heap doesn’t care about the priority between two siblings. For example, is a perfect max-heap, though the left child is smaller than the right child.
- For any element at index , the index to its parent is , and the indices to its left and right children are and .
- For a binary heap of size , its last non-leaf node is at , and its first leaf node is at .
A binary heap must have two fundamental housekeeping functions:
Sift Uptakes a leaf node in the heap, checks whether it should have a higher priority than its parent, swaps them if true, and works its way up in a chain reaction, until no more swaps are possible. This is needed to maintain the heap property when when a new element is pushed to the end of the heap.Sift Downtakes any non-leaf node in the heap, checks whether its priority is lower than one of its children, and, if so, swaps its value with the larger child’s, then works its way down in a chain reaction until no more swaps are possible. This is needed to maintain its heap property when the highest priority item has just been popped.
The following example depicts a max-heap:
import "cmp"
// MaxHeap is our type.
type MaxHeap[T cmp.Ordered] struct {
items []T
}
// Len returns the size.
func (m *MaxHeap[T]) Len() int {
return len(m.items)
}
// Peek returns the max element at index 0 if present.
func (m *MaxHeap[T]) Peek() (max T, ok bool) {
if len(m.items) == 0 {
return max, false
}
return m.items[0], true
}
// Pop removes the max element at index 0 if present
// and restores the max heap property with a sift down.
func (m *MaxHeap[T]) Pop() (max T, ok bool) {
size := len(m.items)
if size == 0 {
return max, false
}
max = m.items[0]
// The last leaf node is moved to index 0
// before shrinking the slice
m.items[0] = m.items[size-1]
clear(m.items[size-1:])
m.items = m.items[:size-1]
m.siftDown(0) // this finds the new max and restores max heap
return max, true
}
// Push adds a element at the tail and restores the
// max heap with a sift up.
func (m *MaxHeap[T]) Push(x T) {
m.items = append(m.items, x)
// Sift up sends the newly added item to where it belongs
m.siftUp(len(m.items)-1)
}
func (m *MaxHeap[T]) siftDown(idx int) {
size := len(m.items)
for {
left := idx*2+1
if left >= size {
break // no leaf to sift down with
}
right := left+1
largest := idx
// use cmp.Less to handle NaN for float64
if cmp.Less(m.items[largest], m.items[left]) {
largest= left
}
// use cmp.Less to handle NaN for float64
if right < size && cmp.Less(m.items[largest], m.items[right]) {
largest= right
}
if largest== idx {
break // nothing to swap
}
m.items[idx], m.items[largest] = m.items[largest], m.items[idx]
idx = largest // sets up chain reaction
}
}
func (m *MaxHeap[T]) siftUp(idx int) {
for idx > 0 {
parent := (idx-1)/2
// use cmp.Less to handle NaN for float64
if !cmp.Less(m.items[parent], m.items[idx]) {
break // nothing to swap
}
m.items[idx], m.items[parent] = m.items[parent], m.items[idx]
idx = parent // sets up chain reaction
}
}There’s one more function that can be useful with a binary heap, and it’s called heapification. It turns an arbitrary complete binary tree that’s not necessarily a binary heap into one. We won’t implement it here. But it achieves heapification by traversing through every non-leaf element in the tree in reverse order, i.e., from down to 0, and performing sift-down on them one by one.
For illustration only:
for i := len(items)/2 - 1; i >= 0; i-- {
siftDown(i)
}What about the complexity?
| Operation | Time complexity | Auxiliary space |
|---|---|---|
| Push (sift-up) | ||
| Pop (sift-down) | ||
| Heapify (bottom-up sift-down) |
* Slice append in Go might end up using space for array relocation.