最大堆和最小堆

您所在的位置：网站首页 › 最小二叉堆 › 最大堆和最小堆

最大堆和最小堆

#最大堆和最小堆| 来源: 网络整理| 查看: 265

标签（空格分隔）：数据结构与算法

定义:

它是一颗完全二叉树,它可以是空树中结点的值总是不大于或者不小于其孩子结点的值每一个结点的子树也是一个堆

当父结点的键值总是大于或等于任何一个子结点的键值时为:最大堆,当父结点的键值总是小于或等于任何一子节点的键值时:最小堆.

下面我们以最大堆来为例作为讲解下图就是一个最大堆

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 ((tmpElement[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 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

【本文地址】

最大堆和最小堆

最大堆和最小堆

今日新闻

推荐新闻