当前位置 博文首页 > ice_elephant的博客：数据结构算法之堆的应用
比武招亲，为古代的招亲方式之一，由女方设下擂台，邀请公众参与，候选人以武功最好者 获得婚约。通常有两种形式：一是擂主由招亲的女生担任，谁挑战成功就成为新擂主。没人再比 试的话直接获得婚约；要是还有人比试，武功最好者获得婚约。二是自由擂主，武功最高者成为 擂主！
这种擂台式的结婚有如下优点和缺点： 优点：可以找个猛男保镖保护，甚至一起闯荡江湖，四海为家 缺点: 不怕找个东方不败，就怕找个像同治帝一样的得了“怪病”
/*
加油！聂宗其！，高处不胜寒，岁寒知松柏。
1、堆的初始化
2、堆的adjustDown
3、堆的adjustUp
4、堆的insert
5、堆的bulid
6、堆出列最大值
7、实现堆的前N个数的堆排列
*/
#include<stdio.h>
#include<Windows.h>
#define DEFAULT_CAPICITY 128
typedef struct _Heap{
int *arr;
int capcity;//容量
int size; //当前元素的个数.数组形式即为下标减1
}Heap;
bool initStack(Heap &heap,int size,int *original);
void adjustDown(Heap &heap,int index);
void adjustUp(Heap &heap,int index);
void bulidStack(Heap &heap);
bool insertdate(Heap &heap,int value);
//初始化堆栈
bool initStack(Heap &heap,int size,int *original){
int capcity = size>DEFAULT_CAPICITY?size:DEFAULT_CAPICITY;
heap.arr = new int[capcity];
heap.capcity = capcity;
heap.size=0;
if(!heap.arr) return false;
//初始化堆
if(size>0){
heap.size = size;
memcpy(heap.arr,original,sizeof(int)*heap.size);
bulidStack(heap);
}
return true;
}
//将当前结点和它的兄弟结点创建堆
void adjustDown(Heap &heap,int index){
if(index<0||index>heap.size) return ;
int child,parent;
//why not parent - index-1/2
//就是把当前结点当作是父结点，求子节点
for(parent = index;(2*parent+1)<heap.size;parent = child){
child = parent*2+1;//根据传入
if(heap.arr[child+1]&&heap.arr[child]<heap.arr[child+1]){
child++;
}
if(heap.arr[parent]<heap.arr[child]){
int tmp = heap.arr[parent];
heap.arr[parent] = heap.arr[child];
heap.arr[child] = tmp;
}else{
break;
}
}
}
//将当前结点和它的父节点调整为最大堆，
void adjustUp(Heap &heap,int index){
if(index<0||index>heap.size) return;
int parent ;
int child;
while(index>0){//这里的
parent = (index-1)/2;
if(parent<0) break;
child = index;
if(heap.arr[child]>heap.arr[parent]){
int tmp = heap.arr[parent];
heap.arr[parent] = heap.arr[child];
heap.arr[child] = tmp;
index = parent;
}else{
break;
}
}
}
//建立堆,堆排序
void bulidStack(Heap &heap){
//区别这里不是计算的parent = (i-1)/2他们两个不一样heap.size/2-1
for(int i = heap.size/2-1;i>=0;i--){
adjustDown(heap,i);
}
}
//插入元素
bool insertdate(Heap &heap,int value){
if(heap.size==heap.capcity)
{
printf("元素已满，无法插入");
return false;
}
heap.arr[heap.size++] = value;
adjustUp(heap,heap.size-1);//传入的是数组下标
return true;
}
//堆顶元素出列
bool deleteTopdata(Heap &heap){
if(heap.size<=0) {
printf("无元素可出列!\n");
}
heap.arr[0] = heap.arr[heap.size-1];//就是把栈顶元素赋值为栈顶元素
heap.size--; //将size减1
adjustDown(heap,0);
return true;
}
//实现堆中，查找出前N大的数
void rankFrontN(Heap &heap,int N){
//N代表元素的个数
if(!heap.arr) return;
if(heap.size==0){
printf("无元素可以排列!\n");
return ;
}
if(N>=heap.size){
printf("无效N值,N应小于%d!\n",heap.size);
}
for(int i=N/2-1;i>=0;i--){
adjustDown(heap,i);
}
}
int main(){
Heap hp;
int Orig[]={123,22,58,66,456,412,20,12};
if(initStack(hp,sizeof(Orig)/sizeof(Orig[0]),Orig)){
printf("堆初始化成功!\n");
}else{
printf("堆初始化失败!\n");
}
printf("排序前遍历******************\n");
for(int i=0;i<hp.size;i++){
printf("%d\t",hp.arr[i]);
}
printf("\n");
//bulidStack(hp);
printf("插入元素后遍历******************\n");
insertdate(hp,100);
insertdate(hp,10);
insertdate(hp,16);
for(int i=0;i<hp.size;i++){
printf("%d\t",hp.arr[i]);
}
printf("\n");
deleteTopdata(hp);
printf("除去栈顶元素后遍历******************\n");
for(
