> ## Content Index
> Fetch the complete content index at: https://huizhou92.com/llms.txt
> Use this file to discover other available public pages before exploring further.

# Go Internal Data Structure: heap
- URL: https://huizhou92.com/go-internal-data-structure-heap/
- Published: 2024-03-12T16:39:06.000Z
- Updated: 2026-09-08T02:38:05.000Z
- Description: Go Internal Data Structure: heap. Note: Non-members can read the full story in this link . In the Go source code, there is an implementation of the heap da。
- Author: huizhou92
- Tags: #Migrated-1788833207488, #Import 2026-09-08 02:07

> Note: Non-members can read the full story in this [link](https://medium.hxzhouh.com/37feea8d3eb1?source=friends%5Flink&sk=dd7be586e559930e305efd8a8fcb3aad).

In the Go source code, there is an implementation of the [heap](https://github.com/golang/go/blob/19309779ac5e2f5a2fd3cbb34421dafb2855ac21/src/container/heap/heap.go?ref=huizhou92.com) 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**](https://en.wikipedia.org/wiki/Heap%5F%28data%5Fstructure%29?ref=huizhou92.com).

> *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\]*](https://en.wikipedia.org/wiki/Heap%5F%28data%5Fstructure%29?ref=huizhou92.com#cite%5Fnote-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](https://www.coursera.org/learn/algorithms-part1?ref=huizhou92.com). 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.

### Implementation of Go heap

> *Based on Go 1.21.4*

The basic operations of a heap are as follows:

![](https://huizhou92.com/content/images/2026/09/1-nq0iaqbocubax9e_ut0pgw.png)

Now, let's take a look at the implementation of [heap](https://github.com/golang/go/blob/19309779ac5e2f5a2fd3cbb34421dafb2855ac21/src/container/heap/heap.go?ref=huizhou92.com). It's quite simple, with only a `sort` interface and two methods: `push` and `pop`.

```go
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](https://leetcode.com/problems/kth-largest-element-in-an-array/?ref=huizhou92.com)

> *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`

![](https://huizhou92.com/content/images/2026/09/1-okrxreiw00t3vuckp8jkwq.gif)

Produced by the author

#### [692\. Top K Frequent Words](https://leetcode.com/problems/top-k-frequent-words/?ref=huizhou92.com)

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

### Usage of heap in real-world

Go src: The Go language's garbage collector (GC) source code uses a heap. [bandUtilHeap](https://github.com/golang/go/blob/ed817f1c4055a559a94afffecbb91c78e4f39942/src/internal/trace/gc.go?ref=huizhou92.com#L342) and [ValHeap](https://github.com/golang/go/blob/ed817f1c4055a559a94afffecbb91c78e4f39942/src/cmd/compile/internal/ssa/schedule.go?ref=huizhou92.com#L28) in the GC source code both utilize heaps.

Etcd: The [lease](https://github.com/etcd-io/etcd/blob/266a3ba5ecef675bf3ce180e5d6260c1886e2e45/server/lease/lease%5Fqueue.go?ref=huizhou92.com#L18) 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](https://www.dolthub.com/blog/2023-12-01-why-are-go-heaps-confusing/?ref=huizhou92.com) discusses this issue.

What are your thoughts on this matter? Feel free to leave a comment.

[文章索引](/article-index/)