Go - Creating Heaps

Problem: You want to create a min heap data structure.

Solution: Wrap a struct around a slice of elements to represent a heap. After each push or pop on the heap, rearrange the heap structure.

A Heap is a special Tree-based data structure in which the tree is a complete binary tree.

A complete binary tree is a special type of binary tree where all the levels of the tree are filled completely except the lowest level nodes which are filled from as left as possible.

The heap property is defined such that each node in a tree has a key that is greater (or less) than or equal to its parent.

There are two types of heaps. The first is the min heap , where the heap property is such that the key of the parent node is always smaller than that of the child nodes. The second is the max heap , where the heap property, as you would expect, is such that the key of the parent node is always larger than that of the child nodes.

The heap is commonly used as a priority queue. A priority queue, as the name suggests, is a queue where each element is given a priority. Priority queues can be implemented in other ways besides using heaps but heaps are so commonly used that sometimes priority queues are simply called heaps.

The heap functions are simple:
Push
• Add a node to the top of the heap.
Pop
• Take the node at the top of the heap.

A popular heap implementation is the binary heap , where each node has at most two child nodes. Let’s see how a binary heap can be implemented. You might be surprised that heaps are commonly implemented in the same way a queue or a stack is implemented, using a slice!

In the max heap implementation in this recipe, use an integer as the node for simplicity:

type   Heap [ T   constraints . Ordered ]   struct   { 
      nodes   [] T 
}

Take a closer look at the list. You can see that 100 is the parent of 19 and 36, 19 is the parent of 17 and 3, and so on. How you find the child node (if any) is basically to double the index of the parent, and add either 1 or 2 (left or right). In other words:

Left child = (2 * parent) + 1

Right child = (2 * parent) + 2

In reverse, to find the parent, subtract 1 from the child and divide by 2. Because it’s a binary tree and it’s an integer, it will return the nearest integer:

parent = (child - 1)/2

func   parent ( i   int )   int   { 
      return   ( i   -   1 )   /   2 
} 

func   leftChild ( i   int )   int   { 
      return   2 * i   +   1 
} 

func   rightChild ( i   int )   int   { 
      return   2 * i   +   2 
}

The two main functions of a heap are also very similar. Push adds a new node to the top of the heap, while pop removes the top of the heap. However, unlike a stack, the node that is returned by pop will always be the smallest or the largest in the heap, depending on whether it’s a min heap or a max heap — that’s how the heap works.

As a result, every time you push or pop an element on the heap, the heap needs to reorganize itself.

func   ( h   * Heap [ T ])   Push ( ele   T )   { 
      h . nodes   =   append ( h . nodes ,   ele ) 
      i   :=   len ( h . nodes )   -   1 
      for   ;   h . nodes [ i ]   >   h . nodes [ parent ( i )];   i   =   parent ( i )   { 
          h . swap ( i ,   parent ( i )) 
      } 
}

The algorithm for push is straightforward. Assuming you’re doing a max heap, this is how it works:
1 Append the new element to the list.
2 Take the last element of the list, and make it the current element.
3 Check if it is larger than the parent. If yes, swap it with the parent.
4 Make the parent the current element and loop until the parent is no longer larger than the current element.

This will result in the newly added node bubbling up the heap until it is at a position where it’s smaller than the parent but larger than both the children.

If you’re concerned about the sibling, don’t be. If it’s larger than the parent, it’ll be larger than the sibling. If it’s not, it doesn’t matter. In a max heap, it doesn’t matter which sibling is left or right as long as both are smaller than the parent. This means there are many possible ways a heap can organize itself.

func   ( h   * Heap [ T ])   Pop ()   ( ele   T )   { 
      ele   =   h . nodes [ 0 ] 
      h . nodes [ 0 ]   =   h . nodes [ len ( h . nodes ) - 1 ] 
      h . nodes   =   h . nodes [: len ( h . nodes ) - 1 ] 
      h . rearrange ( 0 ) 
      return 
}

To recap, pop means you take out the top node of the heap, and you need to reorganize the heap after that. There is a bit more effort for popping the top of the heap, which involves recursion, but it’s quite straightforward too.
This is how it works for a max heap:
1 Take out the top element (this means removing the element at index 0 of the list).
2 Take the last element of the list and move that to the top of the heap.
3 Call the recursive function to rearrange the heap, passing it the index of the top of the heap (this will be 0).

func   ( h   * Heap [ T ])   rearrange ( i   int )   { 
      largest   :=   i 
      left ,   right ,   size   :=   leftChild ( i ),   rightChild ( i ),   len ( h . nodes ) 

      if   left   <   size   &&   h . nodes [ left ]   >   h . nodes [ largest ]   { 
          largest   =   left 
      } 
      if   right   <   size   &&   h . nodes [ right ]   >   h . nodes [ largest ]   { 
         largest   =   right 
      } 
      if   largest   !=   i   { 
          h . swap ( i ,   largest ) 
          h . rearrange ( largest ) 
      } 
} 

func   ( h   * Heap [ T ])   swap ( i ,   j   int )   { 
      h . nodes [ i ],   h . nodes [ j ]   =   h . nodes [ j ],   h . nodes [ i ] 
}

The recursive algorithm works this way:
1 You start, assuming the element at the given index will be the largest.
2 You compare the left and right children of this element with itself.
3 If either the left or right child is larger than itself, you make the left or right child the largest by swapping out the elements and calling the recursive function with the new largest element.

This bubbles the last node down to its natural position. As you’re doing this, you are also forcing the children of the original top of the heap to compare to see which one will go to the top of the heap (it must be either one of them since they are the next largest).

As with other data structures, there are methods to tell the size of the heap and to check if it’s empty or not:

func   ( h   * Heap )   Size ()   int   { 
      return   len ( h . nodes ) 
} 

func   ( h   * Heap )   IsEmpty ()   bool   { 
      return   h . Size ()   ==   0 
}

The standard library’s container package includes a heap package that provides heap operations for any type that implements its interface. If you need a heap, you might also consider using this package.