春招笔记 堆

1.  堆是完全二叉树，根据父节点和子节点的关系，可以分为大根堆和小根堆。    大根堆的父节点比它的所有子节点大，小根堆的父节点比它的所有子节点小。    兄弟节点间不按大小排序。

2.堆是一种结构，逻辑上像完全二叉树，本质上是int型数组，可以将这些值写成树的节点的形式，父亲节点的值比两个孩子的节点，是小根堆

3.判断堆的办法是把序列看成一棵完全二叉树，按层序遍历，若树中的所有非终端节点的值均不大于(或不小于)其左右孩子的节点的值，则该序列为堆。

4.  一般堆排序的话我们都把A[0]作为一个哨兵，不存储实际数据，此时（父节点=子节点/2），而题目要求是A[0]存放的是根节点，则我们可以用相同的转换（父节点=（子节点-1）/2）。

5. 时间复杂度分析，第一步首先建堆需要用时o(n)，第二步对大小为n的堆，取出元素放入数组尾部用时o(1)，重新进行保持堆特性为o(lgn)，因此o(n)+o(nlgn)，总体时间时间复杂度为o(nlgn)

6.  产生堆积现象，即产生了冲突，它对存储效率、散列函数和装填因子均不会有影响，而平均查找长度会因为堆积现象而增大

7.