Data Structures Series IV - Heaps

Heaps are one of the most famous example of non-linear data structures because of the various use-cases where heaps give advantage over other data structures in terms of time and space complexity.

We will be using the example of max-heap where the maximum element is available in O(1) i.e. constant time complexity.

How are heaps created?

Heap elements are stored in an array where for any index i, the left and right children are present at the indices 2 * i + 1 and 2 * i + 2 respectively.

The basic property for max-heaps is that the parent element is always greater than or equal to the children.

For the scope of this blog, we will be focussing on the following operations related to heap.

1. BuildHeap : Builds the heap using in-place array manipulation. After this operation all the elements.
2. Push: Inserts an element in the heap and manipulates in place so that the basic property is maintained after the insertion.
3. Pop: Removes the top element from the heap and retains the properties.
4. Top: Fetches the top element of the heap and returns it.
5. IsEmpty: Returns a boolean to indicate whether the heap is empty or not.

It is time to declare the interface with the methods.

type IHeap interface {
    BuildHeap()
    Push(value int)
    Pop()
    Top() int
    IsEmpty() bool
}

Now, there is a slightly different approach than previous blogs which we will take. Instead of declaring a struct, we will declare a new data type for heap which in essence is a slice of int.

type heap []int

Similar to declaring methods for a struct, we can declare methods for the type heap as well.

There are more helper functions which we will be using for the basic operations. But because these helper methods are not part of the interface, it is not expected that they will directly be referenced in the code.

The first method is to swap any two elements of the heap.

func (h *heap) swap(a,b int) {
    temp := (*h)[a]
    (*h)[a] = (*h)[b]
    (*h)[b] = temp
}

Next is the method which will be used for positioning the elements at the appropriate indices in order to retain the property of the heap.

func (h *heap) percolateUp(pos int) {
    var par int
    par = (pos-1)/2

    for par>-1 && (*h)[pos]>(*h)[par]{
        h.swap(pos,par)
        pos = par
        par = (pos-1)/2
    }
}

Now, we will declare the method which will build the heap from an integer array.

func (h *heap) BuildHeap() {
    n := len(*h)
    for i:=n-1;i>=n/2;i-- {
        h.percolateUp(i)
    }
}

Following it, we define the method to insert an element in a heap. This method ensures that the max-heap is maintained after insertion.

func (h *heap) Push(value int) {
    *h = append(*h,value)
    if len(*h)>1 {
        h.percolateUp(len(*h)-1)
    }
}

Next, we declare the method to fetch the top element of the heap, for our case the maximum element present. It panics in case we try to fetch the top element from an empty heap.

func (h *heap) Top() int {
    if h.IsEmpty() {
        panic("cannot reference to top element of empty heap")
    }
    return (*h)[0]
}

To remove the top element we declare the method which removes the top element and maintains the property of the heap.

func (h *heap) Pop() {
    if h.IsEmpty() {
        panic("cannot pop element from empty heap")
    }
    h.swap(0,len(*h)-1)
    *h = (*h)[:len(*h)-1]
    h.percolateDown(0)
}

For the Pop method to work, we need one more utility method which works from top to bottom and maintains the structure of the heap.

func (h *heap) percolateDown(pos int) {
    maxIdx := pos
    left := 2*pos+1
    right := 2*pos+2

    if left<len(*h) && (*h)[left]>(*h)[maxIdx] {
        maxIdx = left
    }
    if right<len(*h) && (*h)[right]>(*h)[maxIdx] {
        maxIdx = right
    }
    if maxIdx!=pos {
        h.swap(maxIdx,pos)
        h.percolateDown(maxIdx)
    }
}

To end, the method declaration which returns whether the heap is empty of not.

func (h *heap) IsEmpty() bool {
    return len(*h)==0
}

Now we create a function which will accept a list of integers and initialise the heap with integers and returns the heap.

func NewHeap(values ...int) IHeap {
    h := heap{}
    h = append(h,values...)
    h.BuildHeap()
    return &h
}

Example:

func main() {
    // a := NewHeap(10,20) // non empty initialisation
    a := NewHeap() // empty heap initialisation

    a.Push(1)    //1 
    a.Push(9)    //9 1 
    a.Push(3)    //9 1 3 
    a.Push(5)    //9 5 3 1 
    a.Pop()      //5 1 3 
    a.Push(4)    //5 4 3 1 
    a.Push(2)    //5 4 3 1 2 
    a.Pop()      //4 2 3 1 
    a.Push(8)    //8 4 3 1 2 
    a.Pop()      //4 2 3 1 
}

Next steps

Try out the following question on leetcode.com

• Kth Largest Element in a Stream

Additional Functionality

We will add one more algorithm for sorting the elements,which prints all the elements in O(nlog(n)) time complexity in non-increasing order.

func HeapSort(heap IHeap) {
    for !heap.IsEmpty() {
        fmt.Printf("%d ",heap.Top())
        heap.Pop()
    }
}