【数据结构与算法】堆的插入

堆目录

• 一.堆的插入原理
• 二.堆的插入实现
• • 1.数组尾插入数据
  • 2.向上调整成堆
• 三.总结

一.堆的插入原理

上一节我们已经能够创建最大堆了,但是是一个静态的,如果我们插入数据,会产生什么样新的火花呢?

插入一个元素,我们一般插入在末尾来维持前面堆的特点.
很明显,现在的图不是一个最大堆.
开始向上调整:

二.堆的插入实现

1.数组尾插入数据

传入的是新插入元素的下标,不是元素个数.

2.向上调整成堆

先保存子节点的值,然后找到父节点进行对比,然后再把父节点当成子节点,继续向上比较,如果还有父节点的话.

三.总结

插入都是从尾部插入,那么我们建堆又有了一种方法: