In the Go source code, there is an implementation of the heap data structure. Here is its description

// Package heap provides heap operations for any type that implements
// heap.Interface. A heap is a tree with the property that each node is the
// minimum-valued node in its subtree.

What is a heap? In the “Data Structures” course at university, we learned about the classic data structure called a heap. Let’s refresh our memory about heaps through the Wikipedia page.

In computer science, a heap is a tree-based data structure that satisfies the heap property : In a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C. [1] The node at the “top” of the heap (with no parents) is called the root node.

If you haven’t studied computer science or have yet to systematically learn about data structures before, I strongly recommend taking the course Coursera: Algorithms I & II. It is the highest-rated algorithm course on Coursera. Professor Robert Sedgewick has a magical ability to explain even the most complex algorithms clearly and engagingly.

This article is first published in the medium MPP plan. If you are a medium user, please follow me in medium. Thank you very much.

Implementation of Go heap

Based on Go 1.21.4

The basic operations of a heap are as follows:

Now, let’s take a look at the implementation of heap. It’s quite simple, with only a sort interface and two methods: push and pop.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

type Interface interface {
     sort.Interface
     Push(x any) // add x as element Len()
     Pop() any   // remove and return element Len() - 1.
 }
 // sort.Interface  src/sort/sort.go
 type Interface interface {
     // Len is the number of elements in the collection.
     Len() int
     Less(i, j int) bool
     // Swap swaps the elements with indexes i and j.
     Swap(i, j int)
 }

By implementing the sort.Interface, we can obtain a robust heap implementation. Different implementations Less can achieve either a max heap or a min heap. The more complex part of heap maintenance is already implemented in the source code. Since this article is not a data structures course, we won’t delve into the derivation of its principles. Instead, I will use an example to describe the adjustment process.

Example

Now let’s use a heap to solve a practical problem—yes, it’s time to brush up on LeetCode.

215. Kth Largest Element in an Array

Given an integer array nums and an integer k , return the k th largest element in the array. This problem can be perfectly solved using a min heap.

Example 2: Input: nums = [3,2,3,1,2,4,5,5,6], k = 4 Output: 4

692. Top K Frequent Words

The solution is similar; we need to change the implementation of Less.

Usage heap in real-world

• gosrc: The Go language’s garbage collector (GC) source code uses a heap. bandUtilHeap and ValHeap in the GC source code both utilize heaps.

• etcd: The lease implementation in etcd also uses a heap.

Differing Opinions

Some Gophers think heap is difficult to use. Although the standard library provides a heap implementation, it is considered challenging to use for the following reasons:

• It uses a functional approach instead of an intuitive object-oriented approach.
• It requires implementing three methods ( Len, Less, Swap) of the Interface interface ( sort.Interface), as well as Push(x any) and Pop() any.
• The package provides methods such as heap.Init, heap.Fix, heap.Pop, heap.Push, and heap.Remove. The names Pop and Push conflict with the methods of Interface, which can be confusing.
• heap.Pop and Interface.Pop have no relationship, and the same applies to heap.Push and Interface.Push. Although heap.Push internally calls Interface.Push, there are additional processing steps.

However, some people have implemented simpler alternatives. An article titled Why Are Golang Heaps So Complicated discusses this issue.