一、堆： 谈到堆首先要了解二叉树： -二叉树： 顾名思义即每个结点至多有二颗子树（最大度数为2）。树无左右之分，但二叉树有左右之分。第n层最多有2的n次方-1个结点即2 ** n - 1。 二叉树分为： a.空二叉树 b.只有根结点 c.左或右子树空 d.左右子树都不为空 满二叉树： 深度为k，并有2的k次方-1结点的称为满二叉树，即d 完全二叉树： 一颗具有n个结点深度为k的二叉树，和同样深度为k的满二叉树比较，若标号1~n的结点一一对应，即是完全二叉树 二叉树不是树：（理由如下） 树在图论中定义为n-1条边连接n各顶点的图。图的顶点集合非空，故树的顶点非空。图论中定义了N叉树，它可以是空树。 -二叉树的存储： 完全二叉树： 用数组存储，最节省空间、最简单的存储方式。结点下标是从零开始的。i结点的下标为i，即第0个结点的下标为0，第n个结点的下标为n。 其左右子树结点的下标则为 2 * i + 1 和 2 * i + 2 。 一般二叉树： 它为了能够反映二叉树节点的关系，因此也要仿照完全二叉树进行数组编号。故存储则浪费大量的空间，数组中会有很多空值。 因此通常利用二叉链表的形式存储分为 -- 左子女指针域：lchild、数据域：data、右子女指针域：rchild。 若用三叉链表则要再增加一个父指针域指定parent。 -二叉堆： 1．父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。（大于子结点则是最大堆） 2．每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆，也称大根堆和小根堆）。 其它几种堆（二项式堆，斐波纳契堆等）用的较少，一般将二叉堆就简称为堆。二、堆的系列操作 1.堆的概念及存储 如上，二叉堆，一般都用数组来表示堆，是采用完全二叉树的顺序存储方式存储。 Heap-堆结构： #define HeapSize 128 typedef struct minHeap{ #小根堆定义 HElemType heap[HeapSize]; #存放小根堆中元素的数组 int n #小根堆当前元素的个数 } 2.堆的建立： 先视为完全二叉树顺序存储，此时它并不满足是一个小根堆或是大根堆。故要进一步调整为堆化树。 例：现有元素初始排列为{53,17,78,09,45,65,87,23}，初次结构如下，但是初始的树不满足大根堆和小根堆的条件，因此调整如下：如上即初步调整成为小根堆。
转载于:https://www.cnblogs.com/igarashiTR/p/8993729.html
