堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象，即是一种顺序储存结构的完全二叉树。
完全二叉树：对一棵深度为k、有n个结点二叉树编号后，各节点的编号与深度为k的满二叉树相同位置的结点的编号相同，这颗二叉树就被称为完全二叉树。[2]
最大堆：根结点的键值是所有堆结点键值中最大者，且每个结点的值都比其孩子的值大。
最小堆：根结点的键值是所有堆结点键值中最小者，且每个结点的值都比其孩子的值小。
int Heap[1024]; //顺序结构的二叉树
若某结点编号为i，且存在左儿子和右儿子，则他们分别对应
Heap[i*2+1]; //左儿子 Heap[i*2+2]; //右儿子
其父节点
Heap[i/2]; //i的父节点
在项目开发中，经常以动态数组形式出现，在本文主要对这种形式进行介绍
//默认容量 #define DEFAULT_CAPCITY 128 typedef struct _Heap { int *arr; //储存元素的动态数组 int size; //元素个数 int capacity; //当前存储的容量 }Heap; 只使用InitHeap()函数进行初始化即可，AdjustDown()与BuildHeap()仅为堆建立时的内部调用
//向下调整，将当前结点与其子结点调整为最大堆 //用static修饰禁止外部调用 static void AdjustDown(Heap& heap, int index) { int cur = heap.arr[index]; //当前待调整结点 int parent, child; /* 判断是否存在子结点大于当前结点。 若不存在，堆是平衡的，则不调整； 若存在，则与最大子结点与之交换，交换后该子节点若还有子结点，则以此方法继续调整。 */ for (parent = index; (parent * 2 + 1) < heap.size; parent = child) { child = parent * 2 + 1; //左子结点 //取两个子结点中最大节点,(child+1)<heap.size防止越界 if (((child + 1) < heap.size && (heap.arr[child] < heap.arr[child + 1]))) child++; //判断最大子结点是否大于当前父结点 if (cur >= heap.arr[child]) //将此处的>=改成<=可构建最小堆 { //不大于，不需要调整 break; } else { //大于，则交换 heap.arr[parent] = heap.arr[child]; heap.arr[child] = cur; } } } //建立堆，用static修饰禁止外部调用 static void BuildHeap(Heap& heap) { int i; //从倒数第二层开始调整（若只有一层则从该层开始） for (i = heap.size / 2 - 1; i >= 0; i--) { AdjustDown(heap, i); } } //初始化堆 //参数：被初始化的堆，存放初始数据的数组， 数组大小 bool InitHeap(Heap &heap, int *orginal, int size) { //若容量大于size，则使用默认量，否则为size int capacity = DEFAULT_CAPCITY>size?DEFAULT_CAPCITY:size; heap.arr = new int[capacity]; //分配内存，类型根据实际需要可修改 if(!heap.arr) return false; //内存分配失败则返回False heap.capacity = capacity; //容量 heap.size = 0; //元素个数置为0 //若存在原始数组则构建堆 if(size>0) { /* 内存拷贝，将orginal的元素拷贝到堆数组arr中 size*sizeof(int)为元素所占内存空间大小 */ memcpy(heap.arr,orginal, size*sizeof(int)); heap.size = size; //调整大小 BuildHeap(heap); //建堆 } return true; } //以树状的形式打印堆 void PrintHeapAsTreeStyle(Heap hp) { queue<int> que; int r = 0; que.push(r); queue<int> temp; while (!que.empty()) { r = que.front(); que.pop(); if (r * 2 + 1 < hp.size) temp.push(r * 2 + 1); if (r * 2 + 2 < hp.size) temp.push(r * 2 + 2); if (que.empty()) { cout << hp.arr[r] << endl; que = temp; temp = queue<int>(); } else cout << hp.arr[r] << " "; } } int main() { Heap hp; int vals[] = { 1,2,3,87,93,82,92,86,95 }; if (!InitHeap(hp, vals, sizeof(vals) / sizeof(vals[0]))) { fprintf(stderr, "初始化堆失败！\n"); exit(-1); } PrintHeapAsTreeStyle(hp); return 0; } 95 93 92 87 1 82 3 86 2
#include <iostream> #include <queue> using namespace std; //默认容量 #define DEFAULT_CAPCITY 128 typedef struct _Heap { int* arr; int size; int capacity; }Heap; //向下调整，将当前结点与其子结点调整为最大堆 static void AdjustDown(Heap& heap, int index) { int cur = heap.arr[index]; //当前待调整结点 int parent, child; /* 判断是否存在子结点大于当前结点。 若不存在，堆是平衡的，则不调整； 若存在，则与最大子结点与之交换，交换后该子节点若还有子结点，则以此方法继续调整。 */ for (parent = index; (parent * 2 + 1) < heap.size; parent = child) { child = parent * 2 + 1; //左子结点 //取两个子结点中最大节点,(child+1)<heap.size防止越界 if (((child + 1) < heap.size && (heap.arr[child] < heap.arr[child + 1]))) child++; //判断最大子结点是否大于当前父结点 if (cur >= heap.arr[child]) //将此处的>=改成<=可构建最小堆 { //不大于，不需要调整 break; } else { //大于，则交换 heap.arr[parent] = heap.arr[child]; heap.arr[child] = cur; } } } //建立堆，用static修饰禁止外部调用 static void BuildHeap(Heap& heap) { int i; //从倒数第二层开始调整（若只有一层则从该层开始） for (i = heap.size / 2 - 1; i >= 0; i--) { AdjustDown(heap, i); } } //初始化堆 //参数：被初始化的堆，存放初始数据的数组， 数组大小 bool InitHeap(Heap& heap, int* orginal, int size) { //若容量大于size，则使用默认量，否则为size int capacity = DEFAULT_CAPCITY > size ? DEFAULT_CAPCITY : size; heap.arr = new int[capacity]; //分配内存，类型根据实际需要可修改 if (!heap.arr) return false; //内存分配失败则返回False heap.capacity = capacity; //容量 heap.size = 0; //元素个数置为0 //若存在原始数组则构建堆 if (size > 0) { /* 内存拷贝，将orginal的元素拷贝到堆数组arr中 size*sizeof(int)为元素所占内存空间大小 */ memcpy(heap.arr, orginal, size * sizeof(int)); heap.size = size; //调整大小 BuildHeap(heap); //建堆 } return true; } //以树状的形式打印堆 void PrintHeapAsTreeStyle(Heap hp) { queue<int> que; int r = 0; que.push(r); queue<int> temp; while (!que.empty()) { r = que.front(); que.pop(); if (r * 2 + 1 < hp.size) temp.push(r * 2 + 1); if (r * 2 + 2 < hp.size) temp.push(r * 2 + 2); if (que.empty()) { cout << hp.arr[r] << endl; que = temp; temp = queue<int>(); } else cout << hp.arr[r] << " "; } } int main() { Heap hp; int vals[] = { 1,2,3,87,93,82,92,86,95 }; if (!InitHeap(hp, vals, sizeof(vals) / sizeof(vals[0]))) { fprintf(stderr, "初始化堆失败！\n"); exit(-1); } PrintHeapAsTreeStyle(hp); return 0; }