数据结构中什么是大根堆简单理解构建和操作最大堆

导读堆，一维数组，用完全二叉树去描述和分析。各层之间数组下标的规律：parent=child/2。根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者，称为....

堆，一维数组，用完全二叉树去描述和分析。

各层之间数组下标的规律：parent=child/2。

根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者，称为大根堆，又称最大堆（大顶堆）。

入堆，插入：向上渗透（先是插入堆的最后位置，然后按最大堆的规则调整到适当位置）；

出堆，删除：向下渗透（第一个元素出堆，从第二层开始，较大的元素往上渗透，将最后一个元素赋值给倒数第二层上的当前元素。

#include <iostream>using namespace std;const int MAX = 55;typedef struct Heap{int sizeHeap;int* heapData;}HEAP,*LPHEAP;LPHEAP createHeap(){LPHEAP heap=(LPHEAP)malloc(sizeof(HEAP));heap->sizeHeap=0;heap->heapData=(int*)malloc(sizeof(int)*MAX);return heap;}int size(LPHEAP heap){return heap->sizeHeap;}int empty(LPHEAP heap){return heap->sizeHeap==0;}void moveToCorrectPos(LPHEAP heap, int curPos)//向上渗透，curPos一般取最后一个元素的下标{while(curPos>1){int Max=heap->heapData[curPos];int parentIndex=curPos/2;if(Max>heap->heapData[parentIndex]){heap->heapData[curPos]=heap->heapData[parentIndex];heap->heapData[parentIndex]=Max;curPos=parentIndex;//向上移动}else{//break;}}}void insertHeap(LPHEAP heap, int data) //放到当前堆的最后面并按条件往上移{ heap->sizeHeap;heap->heapData[heap->sizeHeap]=data;moveToCorrectPos(heap,heap->sizeHeap);}int popHeap(LPHEAP heap){int Max=heap->heapData[1];int curPos=1;int childIndex=curPos*2;while(childIndex<=heap->sizeHeap){int temp = heap->heapData[childIndex];if(childIndex 1<=heap->sizeHeap && temp<heap->heapData[childIndex 1]){temp=heap->heapData[ childIndex];}heap->heapData[curPos]=temp;curPos=childIndex;//下移一层childIndex*=2;}heap->heapData[curPos]=heap->heapData[heap->sizeHeap];--heap->sizeHeap;return Max;}void main(){LPHEAP heap=createHeap();for(int i=1;i<11; i){insertHeap(heap,i);}for(i=1;i<11; i){printf("%d\t",heap->heapData[i]);}printf("\n");while(!empty(heap)){printf("%d\t",popHeap(heap));} system("pause");}/*10 9 6 7 8 2 5 1 4 310 9 8 7 6 5 4 3 2 1*/

－End－