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

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

各层之间数组下标的规律：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 3 10 9 8 7 6 5 4 3 2 1 */

－End－