资讯详情

堆

1、插入元素

• 上滤

每一次与父亲比较，满足大小就往上交换，直至不能往上为止。

每次往上交换不会影响下面的性质

---

2、删除/输出堆顶

• 下滤

假设大根堆，根节点换入末尾节点，每次先找出大儿子，若大儿子比自己大，则往下和他交换，直至不能往下为止。

3、建堆

1）初始为空，逐个insert，如 上滤 一般操作

2）初始乱序，则从末尾开始。假设大根堆，左右儿子比出好大儿，和父亲比较，大就往上交换，不然不操作。 继续下一个家庭同样操作。从倒数第二层开始，每次若能交换，换下来的元素可能影响以他为父亲的树的堆性 质，因此，若影响，则对该节点下滤。然后继续前面的操作。