Algorithms and Data Structures - Heap

This article was originally published on bmf-tech.com.

Overview

Referencing Algorithm Encyclopedia, I am learning algorithms and data structures.

The implementation is also available on github - bmf-san/road-to-algorithm-master.

Heap

• A type of priority queue
  • A priority queue is a data type that handles a set
  • Elements contained in the set are retrieved in order of priority
  • Examples of data types that handle sets: queue, stack
• Types of heaps
  • Min heap
  • A heap where the root is always the smallest. The parent node is always smaller than the child nodes.
  • Max heap
  • A heap where the root is always the largest element. The parent node is always larger than the child nodes.

Computational Time

• Both addition and deletion are O(log n)

Implementation

package main

import "fmt"

// Heap is a heap.
type Heap struct {
    values  []int
    size    int
    maxsize int
}

// newHeap creates a heap.
func newHeap(maxsize int) *Heap {
    return &Heap{
        values:  []int{},
        size:    0,
        maxsize: maxsize,
    }
}

// leaf checks whether index is a leaf.
func (h *Heap) leaf(index int) bool {
    if index >= (h.size/2) && index <= h.size {
        return true
    }
    return false
}

// parent checks whether index is a parent.
func (h *Heap) parent(index int) int {
    return (index - 1) / 2
}

// leftchild checks whether index is a leftchild.
func (h *Heap) leftchild(index int) int {
    return 2*index + 1
}

// rightchild checks whether index is a rightchild.
func (h *Heap) rightchild(index int) int {
    return 2*index + 2
}

// insert inserts a item to a heap.
func (h *Heap) insert(item int) error {
    if h.size >= h.maxsize {
        return fmt.Errorf("Error!")
    }
    h.values = append(h.values, item)
    h.size++
    h.upHeapify(h.size - 1)
    return nil
}

// swap swaps two values.
func (h *Heap) swap(first, second int) {
    temp := h.values[first]
    h.values[first] = h.values[second]
    h.values[second] = temp
}

// upHeapify reconstruct a heap for up.
func (h *Heap) upHeapify(index int) {
    for h.values[index] < h.values[h.parent(index)] {
        h.swap(index, h.parent(index))
    }
}

// downHeapify reconstruct a heap for down.
func (h *Heap) downHeapify(current int) {
    if h.leaf(current) {
        return
    }

    smallest := current
    leftChildIndex := h.leftchild(current)
    rightRightIndex := h.rightchild(current)

    if leftChildIndex < h.size && h.values[leftChildIndex] < h.values[smallest] {
        smallest = leftChildIndex
    }
    if rightRightIndex < h.size && h.values[rightRightIndex] < h.values[smallest] {
        smallest = rightRightIndex
    }
    if smallest != current {
        h.swap(current, smallest)
        h.downHeapify(smallest)
    }
    return
}

// buildMinHeap builds a min heap.
func (h *Heap) buildMinHeap() {
    for index := ((h.size / 2) - 1); index >= 0; index-- {
        h.downHeapify(index)
    }
}

// remove removes a value.
func (h *Heap) remove() int {
    top := h.values[0]
    h.values[0] = h.values[h.size-1]
    h.values = h.values[:(h.size)-1]
    h.size--
    h.downHeapify(0)
    return top
}

func main() {
    inputArray := []int{6, 5, 3, 7, 2, 8}
    h := newHeap(len(inputArray))
    for i := 0; i < len(inputArray); i++ {
        h.insert(inputArray[i])
    }
    h.buildMinHeap()
    for i := 0; i < len(inputArray); i++ {
        fmt.Println(h.remove())
    }
    fmt.Scanln()
}

• Implementation of min heap
• Nodes are always added in breadth-first order
• After adding a node, if the added value is smaller than the root node, swap the root node with the added node
• It's easy to understand by checking the image at Data Structure Visualizations - Min Heap
• Calculations for root, parent, left child node, and right child node are characteristic
  • Since the array index becomes the priority, the values of these nodes can be derived from the reference node through calculations
  • The article Explaining Heap Clearly is easy to understand
• Referenced Welcome To Golang By Example - Heap in Golang (mostly transcribed..)

References

• Explaining Heap Clearly
• Welcome To Golang By Example - Heap in Golang