数据结构之——堆（Heap）_heap数据结构

堆（Heap）

堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。同时堆是一种特殊的“队列”

完全二叉树

既然说堆是完全二叉树，那么就得介绍下什么是完全二叉树

定义：若设二叉树的高度为h，除第h层外，其它各层（1～h-1）的结点数都达到最大个数，且第h层所有的节点都连续集中在最左边，这就是完全二叉树。

完全二叉树是由满二叉树而引出来的。对于深度为K，有N个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

若一棵二叉树至多只有最下面两层的结点的度数可以小于2，并且最下层的结点都集中在该层最左边的若干位置上，则此二叉树为完全二叉树。

完全二叉树的性质

1. 设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，则n0=n2+1
2. n层完全二叉树，在1~n-1层，节点个数为2^(n-1),在第n层，节点数范围为[1,2 ^ (n-1)]

堆的特点

堆的两个特性：

1. 结构性：用数组表示的完全二叉树
2. 任意节点的关键字是其子树所有节点的最大值（或者最小值）
   • “最大堆（Max Heap）”也称大顶堆：最大值
   • “最小堆（Min Heap）”也称小顶堆：最小值

最大堆

最小堆

把最大堆和最小堆的逻辑结构映射到数组中，如下图

数组arr下标从零开始
对于最大堆：arr[i] >= arr[2i + 1] && arr[i] >= arr[2i + 2]

对于最小堆：arr[i] <= arr[2i + 1] && arr[i] <= arr[2i + 2]

Ps:此篇文章主要供自己复习所用，若读者发现错误，欢迎跟我指出