2.10 heap

1. What Is a Heap

Logically it can be viewed as a tree, but physically it is an array.

• Position relationships When the array starts at index 0:
  • The left child of parent node i is at 2 * i + 1
  • The right child of parent node i is at 2 * i + 2
  • The parent of child node i is at (i - 1) / 2
• Ordering property
  • Max heap: parent value >= left/right child values
  • Min heap: parent value <= left/right child values

2. Max Heap

2.1. Data Structure

• Dynamic array

2.2. API

type IMaxHeap interface {
	// Print all elements in the max heap
	String() string
	// Get the number of elements in the max heap
	Length() int
	// Whether the max heap is empty
	IsEmpty() bool
	// Add an element to the max heap O(logN)
	Add(e model.Comparable) error
	// Remove the largest element from the max heap O(logN)
	ExtractMax() (model.Comparable, error)
	// Get the largest element in the max heap
	FindMax() (model.Comparable, error)
}

2.3. Implementation

const NonExists = -1

type MaxHeap struct {
	array array.IArray
}

func NewMaxHeap(data ...model.Comparable) *MaxHeap {
	newArray := array.NewArray()
	for _, e := range data {
		_ = newArray.AddLast(e)
	}

	m := &MaxHeap{array: newArray}
	m.heapify()
	return m
}

func (m *MaxHeap) String() string {
	return fmt.Sprintf("array: %v", m.array)
}

func (m *MaxHeap) Length() int {
	return m.array.Length()
}

func (m *MaxHeap) IsEmpty() bool {
	return m.array.IsEmpty()
}

func (m *MaxHeap) Add(e model.Comparable) error {
	// First insert at the end
	_ = m.array.AddLast(e)
	// The newly inserted element may be the largest
	// Adjust upward from this element -- move larger values upward
	m.siftUp(m.Length() - 1)
	return nil
}

// Get the parent index
func (m *MaxHeap) parent(index int) (int, error) {
	if index <= 0 {
		return NonExists, fmt.Errorf("out of bound")
	}

	return (index - 1) / 2, nil
}

// Get the left-child index
func (m *MaxHeap) leftChild(index int) int {
	return index*2 + 1
}

// Get the right-child index
func (m *MaxHeap) rightChild(index int) int {
	return index*2 + 2
}

func (m *MaxHeap) ExtractMax() (model.Comparable, error) {
	max, err := m.FindMax()
	if err != nil {
		return nil, err
	}
	m.swap(0, m.array.Length()-1)
	_, _ = m.array.RemoveLast()
	// After moving the last element to the top, this element may be the smallest
	// Adjust downward from this element -- move smaller values downward
	m.siftDown(0)

	return max, nil
}

func (m *MaxHeap) FindMax() (model.Comparable, error) {
	if m.IsEmpty() {
		return nil, fmt.Errorf("heap is empty")
	}

	return m.array.Get(0)
}

func (m *MaxHeap) siftUp(childIndex int) {

	for childIndex > 0 {
		parentIndex, _ := m.parent(childIndex)
		parent, _ := m.array.Get(parentIndex)
		child, _ := m.array.Get(childIndex)

		if child.CompareTo(parent) <= 0 {
			break
		}

		m.swap(parentIndex, childIndex)

		childIndex = parentIndex
	}
}

func (m *MaxHeap) swap(i int, j int) {
	a, _ := m.array.Get(i)
	b, _ := m.array.Get(j)
	_ = m.array.Set(i, b)
	_ = m.array.Set(j, a)

}

func (m *MaxHeap) siftDown(parentIndex int) {
	// Stop at half because nodes from here have no children
	half := m.array.Length() / 2
	for parentIndex < half {
		leftChildIndex := m.leftChild(parentIndex)
		rightChildIndex := m.rightChild(parentIndex)

		// First assume the left child is the largest
		maxIndex := leftChildIndex
		maxChild, _ := m.array.Get(maxIndex)
		// If the right child exists and is larger, update maxXXX
		if rightChildIndex < m.Length() {
			rightChild, _ := m.array.Get(rightChildIndex)
			if rightChild.CompareTo(maxChild) > 0 {
				maxChild = rightChild
				maxIndex = rightChildIndex
			}
		}

		parent, _ := m.array.Get(parentIndex)
		if maxChild.CompareTo(parent) <= 0 {
			break
		}

		// Swap the parent and the larger child
		m.swap(parentIndex, maxIndex)
		parentIndex = maxIndex
	}

}

// O(N)
func (m *MaxHeap) heapify() {
	// Start from nodes with children and sift down to maintain the heap property
	for i := m.array.Length()>>1 - 1; i >= 0; i-- {
		m.siftDown(i)
	}
}

2.3.1. Test

func TestHeap(t *testing.T) {
	e1 := model.NewElement(1)
	e2 := model.NewElement(2)
	e3 := model.NewElement(3)
	e4 := model.NewElement(4)
	e5 := model.NewElement(5)

	heap := NewMaxHeap(e1, e2, e3, e4, e5)
	fmt.Println(heap)

	for i := 5; i < 10; i++ {
		e := model.NewElement(i)
		_ = heap.Add(e)
	}
	fmt.Println(heap)

	for !heap.IsEmpty() {
		max, _ := heap.ExtractMax()
		fmt.Println(max)
	}

}

3. Min Heap

Property: parent value <= left/right child values

• Build heap

  • Start from the rightmost leaf node, perform sift-up, and continue until halfway
  • Or start from the rightmost node that has children, perform sift-down, and continue to the root node

• Insert

  • Insert the value at the end of the array (the rightmost leaf node), then sift up to maintain the min-heap property

• Delete

  • Remove the first array element (the root), put the last array element at the first position (move the rightmost leaf to the root), then sift down to maintain the min-heap property

4. Implementation

PriorityQueue.md