数据结构之——堆（Heap）
堆（Heap）
堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。同时堆是一种特殊的“队列”
完全二叉树
既然说堆是完全二叉树，那么就得介绍下什么是完全二叉树
定义：若设二叉树的高度为h，除第h层外，其它各层（1～h-1）的结点数都达到最大个数，且第h层所有的节点都连续集中在最左边，这就是完全二叉树。
完全二叉树是由满二叉树而引出来的。对于深度为K，有N个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
若一棵二叉树至多只有最下面两层的结点的度数可以小于2，并且最下层的结点都集中在该层最左边的若干位置上，则此二叉树为完全二叉树。
完全二叉树的性质
- 设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，则n0=n2+1
- n层完全二叉树，在1~n-1层，节点个数为2^(n-1),在第n层，节点数范围为[1,2 ^ (n-1)]
堆的特点
堆的两个特性：
- 结构性：用数组表示的完全二叉树
任意节点的关键字是其子树所有节点的最大值（或者最小值）
- “最大堆（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:此篇文章主要供自己复习所用，若读者发现错误，欢迎跟我指出
青旅半醒
分手后的思念是犯贱
港控/mmm°
ゞ 浴缸里的玫瑰
迷南。
还没有评论，来说两句吧...