heapify()

前面两篇文章介绍了什么是堆以及堆的两个基本操作，但其实呢，堆还有一个大名鼎鼎的非常重要的操作，就是 heapify() 了，它是一个很神奇的操作，

可以用 O(n) 的时间把一个乱序的数组变成一个 heap。

但是呢，heapify() 并不是一个 public API，看：

所以我们没有办法直接使用。

唯一使用 heapify() 的方式呢，就是使用
PriorityQueue(Collection<? extends E> c)

这个 constructor 的时候，人家会自动调用 heapify() 这个操作。

那具体是怎么做的呢？

哈哈源码已经暴露了：

从最后一个非叶子节点开始，从后往前做 siftDown().

因为叶子节点没必要操作嘛，已经到了最下面了，还能和谁 swap？

举个例子：

我们想把这个数组进行 heapify() 操作，想把它变成一个最小堆，拿到它的最小值。

那就要从 3 开始，对 3，7，5进行 siftDown().

Step 1.

尴尬

版权声明：本文为nycsde原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/nycsde/p/13838180.html