6.9.二叉堆操作

我们的二叉堆实现的基本操作如下：

  • BinaryHeap() 创建一个新的，空的二叉堆。
  • insert(k) 向堆添加一个新项。
  • findMin() 返回具有最小键值的项，并将项留在堆中。
  • delMin() 返回具有最小键值的项，从堆中删除该项。
  • 如果堆是空的，isEmpty() 返回 true，否则返回 false。
  • size() 返回堆中的项数。
  • buildHeap(list) 从键列表构建一个新的堆。ActiveCode 1 展示了使用一些二叉堆方法。注意，无论我们向堆中添加项的顺序是什么，每次都删除最小的。我们现在将把注意力转向如何实现这个想法。
  1. from pythonds.trees.binheap import BinHeap
  3. bh = BinHeap()
  4. bh.insert(5)
  5. bh.insert(7)
  6. bh.insert(3)
  7. bh.insert(11)
  9. print(bh.delMin())
  11. print(bh.delMin())
  13. print(bh.delMin())
  15. print(bh.delMin())