
背景知识
知道什么是大堆/小堆
掌握如何将数组与完全二叉树的映射关系
掌握向上调整法和向下调整法
大堆/小堆大堆的特性:每一个节点的值都比左右孩子都大,根的值是整个大堆中最大的小堆的特性:每一个节点的值都比左右孩子都小,根的值是整个大堆中最小的
后面以大堆为例
数组映射成完全二叉树任何一个数组可以看成一个完全二叉树,下标0为二叉树的根
而非常方便的是,已知一个节点的下标,可以利用数学关系求出根或孩子的下标
下标关系如下(变量均为下标)
parent = (child-1)/2
left_child = parent*2+1
right_child = parent*2+2
建堆方法向上调整法在已有一个大堆的前提下,把一个新的数据插入到堆的最后一个节点(此时破坏大堆的结构),再一路向上调整,可以重新建堆
123456789101112131415161718template<class T>void adjust_up(vector<T>& arr, int child){ int parent = (child - ...