标签（空格分隔）： 数据结构与算法
定义:
- 它是一颗完全二叉树,它可以是空
- 树中结点的值总是不大于或者不小于其孩子结点的值
- 每一个结点的子树也是一个堆
当父结点的键值总是大于或等于任何一个子结点的键值时为:最大堆,当父结点的键值总是小于或等于任何一子节点的键值时:最小堆.
下面我们以最大堆来为例作为讲解
下图就是一个最大堆
image.png
构造最大堆
对于一个给定的数据 Arr = {5, 1, 13, 3, 16, 7, 10, 14, 6, 9},如何构造出一个最大堆呢?
首先它是一颗完全二叉树,因此我们可以使用顺序存储.对应的完全二叉树如下图:
image.png
开始构造最大堆:
1.首先我们需要找到最后一个结点的父结点如图(a),我们找到的结点是
16,然后找出该结点的最大子节点与自己比较,若该子节点比自身大,则将两个结点交换.
图(a)中,16是最大的结点,不需要交换.
2.我们移动到第下一个父结点3,如图(b)所示.同理做第一步的操作,交换了3和14,结果如图(c)所示.
3.移动结点到下一个父结点13,如图(d)所示,发现不需要做任何操作,
4.移动到下个父结点1,如图(e)所示,然后交换1和16,如图(f)所示,此时我们发现交换后,1的子节点并不是最大的,我们接着在交换(如图g)所示
5.移动到父结点到5,一次重复上述步骤,交换5和16,在交换14和5,在交换5和6
所有节点交换完毕,最大堆构建完成
image.png
typedef int ElementType;
typedef struct HeapStruct *MaxHeap;
struct HeapStruct {
//指向一个数组
ElementType *Element;
//堆当前元素的个数
int size;
//堆的最大容量
int capacity;
};
int maxIndex(int left, int right, MaxHeap heap);
void initHeap(int *arr, int size, MaxHeap &heap, int maxCapacity) {
heap = (MaxHeap)malloc(sizeof(HeapStruct));
heap->capacity = maxCapacity;
heap->Element = new ElementType[maxCapacity+1];
heap->size = size;
//第一个位置不存任何数据,交换结点时可以作为中间变量
heap->Element[0] = 0;
//构建完全二叉树
for (int i = 0; i < size; i++) {
heap->Element[i+1] = arr[i];
}
//寻找最后一个结点的父结点,作为初始值
for (int pIndex = heap->size / 2; pIndex >= 1; pIndex--) {
int tmp = pIndex;
while ((tmp<<1) <= heap->size) { //表示该结点有孩子结点-->当该结点时叶子结点时,循环结束
//寻找这个结点的最大子结点
int maxChildIndex = 0;
if ((tmp<<1) + 1 > heap->size) { //没有右孩子,则左孩子就是最大子结点
maxChildIndex = (tmp<<1);
} else {//从左右孩子中寻找最大子结点
maxChildIndex = maxIndex(tmp<<1, (tmp<<1) + 1, heap);
}
//比较最大子结点和当前父结点,如果父结点的值小于最大子结点的值,则交换两个结点
if (heap->Element[tmp] < heap->Element[maxChildIndex]) {
//交换两个结点
heap->Element[0] = heap->Element[tmp];
heap->Element[tmp] = heap->Element[maxChildIndex];
heap->Element[maxChildIndex] = heap->Element[0];
heap->Element[0] = 0;
tmp = maxChildIndex;
} else {
break;//当该结点不需要在交换时,结束向下查找
}
}
}
}
int maxIndex(int left, int right, MaxHeap heap) {
return heap->Element[left] > heap->Element[right] ? left : right;
}
最大堆中插入一个结点
原理:现在堆的最后增加一个结点,然后沿这堆树上升.
int maxHeapInsert(ElementType e, MaxHeap heap) {
//检查是否到达了堆的最大容量
if (heap->capacity == heap->size) {
return -1;
}
heap->size++;
heap->Element[heap->size] = e;
for (int sIndex = heap->size; sIndex > 1;) {
//寻找这个结点的父结点
int pIndex = sIndex / 2;
if (heap->Element[pIndex] < heap->Element[sIndex]) {
heap->Element[0] = heap->Element[pIndex];
heap->Element[pIndex] = heap->Element[sIndex];
heap->Element[sIndex] = heap->Element[0];
heap->Element[0] = 0;
sIndex = pIndex;
} else {
break;
}
}
}
最大堆中删除一个元素
原理:将堆的最后的结点提到根结点，然后删除最大值，然后再把新的根结点向下进行调整,直到找到其符合的的位置.
int maxHeapPopE(MaxHeap heap, ElementType *e) {
if (heap->size == 0) {
return -1;
}
*e = heap->Element[1];
heap->Element[1] = heap->Element[heap->size];
heap->size--;
int pIndex = 1;
while (pIndex <<1 <= heap->size) { //有子结点
int maxChild = 0;
if ((pIndex << 1) + 1 > heap->size) { //没有右孩子
maxChild = pIndex << 1;
} else {
maxChild = maxIndex(pIndex << 1, (pIndex << 1) + 1, heap);
}
if (heap->Element[pIndex] < heap->Element[maxChild]) {
heap->Element[0] = heap->Element[pIndex];
heap->Element[pIndex] = heap->Element[maxChild];
heap->Element[maxChild] = heap->Element[0];
heap->Element[0] = 0;
pIndex = maxChild;
} else {
break;
}
}
}
下面我们测试一下代码
int main() {
int arr[] = { 5, 1, 13, 3, 16, 7, 10, 14, 6, 9 };
MaxHeap heap = nullptr;
initHeap(arr, sizeof(arr) / sizeof(int), heap,20);
maxHeapInsert(18, heap);
ElementType e;
maxHeapPopE(heap, &e);
cout << " e = " << e << endl;
for (int i = 1; i <= heap->size; i++) {
cout << heap->Element[i] << endl;
}
system("pause");
return 0;
}
