关于数据结构笔记——堆

数据结构——堆（Heap）

堆有完全二叉树的特点

①堆必须为一个完全二叉树，所以它的所有结点从上到下、从左到右的排序序号（从1开始）：

当某个结点序号为i，则它的左子结点的序号为2i；右子结点的序号为2i+1。

②因为为完全二叉树，所以：

树的最底层的叶结点只能从右到左的减少，且叶结点之间不能有间隔。

堆的根结点（父结点）在其子树中最大/最小

堆有最大堆和最小堆。

最大堆

最大堆的根结点的值在树中最大，它的左右子树都比它小，其它结点的值都要比各自的左子结点和右子结点大。（图片上方7到1为数组下标为1~7存放的元素）

最小堆

最小堆的根结点的值为树中最小的，它的左右子树都比它大，其它结点也是各自的左右子节点比它们大。（图片上方1到7为数组下标为1~7存放的元素）

将树转换为最大堆/最小堆转为最大堆

将破坏了堆序性的结点（根）与它的左右子结点相比，与比该结点最大的结点对换位置，直到该节点比它的左右子结点都大或者到底为止；
当破坏堆序性的结点在底部（叶结点），则将该结点与它的父结点比较，大于父结点与父结点交换位置，直到不再大于父结点或者到达顶部为止。

转为最小堆

与上面转为最大堆类似，将破坏了堆序性的结点（根）与它的左右子结点相比，与比该结点最小的结点对换位置，直到该节点比它的左右子结点都小或者到底为止；
若破坏堆序性的结点在底部（叶结点），则将该节点与其父结点比较，小于父结点则与它交换位置，直到不再小于父结点或者到达顶部为止。

堆取最大元素/最小元素取最大数

取最大数是在最大堆里取它的根结点，根结点被取走后，原本根结点的位置就由树的最后一个结点代替，然后进行转换为最大堆的步骤（和上面转为最大堆一样），也就是新的根结点与左右子结点比较，与比根结点最大的子结点交换位置，以此类推，直到比左右子结点大或者到底为止。

取最小数

取最小数是在最小堆里取它的根结点，根结点被取走后，原本根结点的位置就由树的最后一个结点代替，然后进行转换为最小堆的步骤（和上面转为最小堆一样），也就是新的根结点与左右子结点比较，与比根结点最小的子结点交换位置，以此类推，直到比左右子结点小或者到底为止。