堆排序(大顶堆)

2020-11-30  本文已影响0人  DFlatMajor

主要是围绕heapify操作

建堆,从下往上对每一个父节点heapify。第一个父节点的下标是  ((n -1)-1)/2,注意不是  (n -1)/2,因为对于偶数节点必须要 -1,否则对应的是旁边的父节点。

排序,每次将顶部节点移动到尾部,然后调整heapify的堆的大小 -1,再做一次heapify。

插入,将一个元素放在尾部,然后一次往上找父节点。找到小的就交换即可。

删除呢,将顶部的丢了(从尾部取一个覆盖),然后size--,再heapify。

上一篇 下一篇

猜你喜欢

热点阅读