背景
最近使用到了 heap 这个数据结构,记录一下在 Python 和 Golang 中最基本的使用方法~
堆(英语:Heap)是计算机科学中的一種特別的樹狀数据结构。若是滿足以下特性,即可稱為堆積:「給定堆積中任意節點P和C,若P是C的母節點,那麼P的值會小於等於(或大於等於)C的值」。若母節點的值恆小於等於子節點的值,此堆積稱為最小堆積(min heap);反之,若母節點的值恆大於等於子節點的值,此堆積稱為最大堆積(max heap)。在堆積中最頂端的那一個節點,稱作根節點(root node),根節點本身沒有母節點(parent node)。
Python
create
1 | In [1]: import heapq |
read
1 | In [28]: b |
update
1 | In [32]: heapq.heappush(b, 6) |
delete
1 | In [50]: b |
Golang
Golang 中没有 heapq 这种封装好的库可以直接使用,不过有 container/heap
,提供了同样的方法,只是我们需要先对我们的操作对象实现搜有的 heap.Interface
方法。
Constructor
1 | // This example demonstrates an integer heap built using the heap interface. |
create
1 | // This example demonstrates an integer heap built using the heap interface. |
read
1 | package main |
update
1 | package main |
delete
1 | // This example demonstrates an integer heap built using the heap interface. |
总结
Heap 的使用场景有:优先级队列、TopK 等等。