基本概念
底层是二叉树,根节点最小(或最大),除最后一分支其他的都满了,数组实现的堆不要求左边的比右边的小。
用数组来维护,索引从1开始,2n 是左节点,2n + 1是右节点
实现功能
插入一个数: 插在数组最后,再往上查找位置
求最小: 根(头)节点
删除最小值: 将最后一个点覆盖到头节点,删掉最后一个,然后往下找自己的位置
为什么呢?因为数组存储很难删掉头元素,但是删掉最后一个很简单,所以通过覆盖掉头元素,直接去掉最后一个元素,再往下down操作找正确位置
删除任意元素: 用最后一个覆盖,再往下找再往上找,其实是此时覆盖之后最后一个元素可能有三种情况(最后一个不一定是最大值):
- 如果大,就往下
- 小就往上 所以直接down一次,up一次
修改元素 直接改,往上找也往下找
具体使用
-
堆排序
- 每次找最小值
- AC_dui_sort.cpp
-
模拟堆