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
.
|
|
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 integerk
, return thek
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 theInterface
interface (sort.Interface
), as well asPush(x any)
andPop() any
. - The package provides methods such as
heap.Init
,heap.Fix
,heap.Pop
,heap.Push
, andheap.Remove
. The namesPop
andPush
conflict with the methods ofInterface
, which can be confusing. heap.Pop
andInterface.Pop
have no relationship, and the same applies toheap.Push
andInterface.Push
. Althoughheap.Push
internally callsInterface.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.