本文主要是介绍堆（最小堆、最大堆、建堆、插入)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
堆是一种特殊的数据结构，是一种完全二叉树，分为最大堆（根节点的值大于孩子节点）和最小堆（根节点小于孩子节点）
不失一般性，只讨论最小堆的情况。
1、插入
只需要将节点插在二叉树的最后一个叶子结点位置，然后比较它对它父亲节点的大小，如果大则停止；如果小则交换位置，然后对父亲节点递归该过程直至根节点。复杂度为O(log(n))。
一般来说，插入的位置可以不是最后一个叶子节点，可以作为任意中间节点的孩子节点插入，将这个叶子节点变为中间节点后，按上文所说的方法调整节点顺序以保证维持堆特性不变。
2、删除
要从堆中删除一个节点，用最后一个节点替换掉根节点，然后调整节点顺序以维持堆特性。
建堆既可以用堆调整方法将原数组调整为一个堆，也可以借助往堆中插入元素的方法从无到有的建立一个堆。
两种方法比较：
（1）借助堆调整建堆的时间复杂度为O(n)。借助插入法建堆的时间复杂度为O(nlgn) ，书上第二问要求证明这个复杂度，但是我认为插入法的复杂度也是O（n），因为它和堆调整的区别在于针对每个节点i，堆调整是自上向下进行调整，插入法是自下向上进行调整。
（2）对于同样的输入两个方法建立的堆可能不同。因为堆调整时，是i要跟它的两个子女进行比较，选出最大（小）的，但是插入x时，x只跟它的父节点进行比较。比如输入为2、3、4，堆调整建堆为4、3、2，插入法建堆为4、2、3。
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;void adjustMinHeap(int* a, int size, int index ){int left, right,least;left = 2*index;right = left + 1;if(left<=size&&a[left]<a[index])least = left;else least = index;if(right<=size&&a[right]<a[least])least = right;if(least!= index){a[index] += a[least];a[least] = a[index] - a[least];a[index] -= a[least];adjustMinHeap(a,size,least);}
}void buildHeap(int* a , int size){int index;for(index = size/2;index >= 1; index--){adjustMinHeap(a,size,index);}
}void add(int*a , int* size , int val){*size = *size+1;int parent = *size/2;int index = *size;a[*size] = val;while(a[index]<a[parent]){a[index] += a[parent];a[parent] = a[index] - a[parent];a[index] -= a[parent];index = parent;parent = index/2;}
}void removeMin(int*a ,int* size){a[1] = a[*size];(*size)--;adjustMinHeap(a,*size,1);
}
void main(){int addi;int size = 10;srand(time(0));int* a =(int *) malloc(100*sizeof(int));*(a+1) = rand() %100;*(a+2) = rand() %100;*(a+3) = rand() %100;*(a+4) = rand() %100;*(a+5) = rand() %100;*(a+6) = rand() %100;*(a+7) = rand() %100;*(a+8) = rand() %100;*(a+9) = rand() %100;*(a+10) = rand() %100;cout<<"before:"<<endl;for(int i =0; i<4;i++){for(int j =(int)(0x01<<i);j<2*(int)(0x01<<i)&&j<=size;j++)cout<< *(a+j) << ",";cout<<endl;}cout<<endl;cout<<"after:"<<endl;buildHeap(a,size);for(i =0; i<4;i++){for(int j =(int)(0x01<<i);j<2*(int)(0x01<<i)&&j<=size;j++)cout<< *(a+j) << ",";cout<<endl;}cout<<endl;cin>>addi;add(a,&size,addi);for(i =0; i<4;i++){for(int j =(int)(0x01<<i);j<2*(int)(0x01<<i)&&j<=size;j++)cout<< *(a+j) << ",";cout<<endl;}removeMin(a,&size);cout<<"after Remove:"<<endl;for(i =0; i<4;i++){for(int j =(int)(0x01<<i);j<2*(int)(0x01<<i)&&j<=size;j++)cout<< *(a+j) << ",";cout<<endl;}
}
这篇关于堆（最小堆、最大堆、建堆、插入)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
