堆！
前面，我们学习了二叉搜索树，今天呢，我们来介绍下堆，堆是什么呢？
堆是用数组实现的二叉树，分为最大堆和最小堆，两者的差别在于节点的排序方式，拿最大堆来说，父节点的值比每一个子节点的值都要大，这就是所谓的“堆属性”，该属性对每一个节点都成立。
堆也是一种重要的数据结构，常用于：
- 构建优先队列
- 堆排序
- 快速找出一个集合中的最小值（或者最大值）
首先，我们来看下堆的结构定义
typedef int ElemType;
typedef struct MaxHead
{ElemType * elements;//元素数组int size;//目前堆中的元素个数int capacity;//堆的容量
}MaxHead;堆的操作集
MaxHead Create(int size);//创建一个堆
bool IsFull(MaxHead head);//判断堆是否已满
bool IsEmpty(MaxHead head);//判断堆是否为空
void Insert(MaxHead * head,ElemType elem);//插入
ElemType DeleteMax(MaxHead * head);//删除
void Build(MaxHead *head,ElemType *data,int n);//建议一个堆
void Printf(MaxHead head);//打印堆中元素其中，插入和删除是最重要的两个操作，我们具体来看一下
插入
void Insert(MaxHead * head,ElemType elem)
{if(IsFull(*head)){//判断堆是否为满cout<<"堆满"<<endl;return ;}int i=++(head->size);//先把待插入元素放入堆的最后一个for(;elem>head->elements[i/2];i/=2)//待插入元素和其父节点大小做比较，一层层的做调整{head->elements[i]=head->elements[i/2];}head->elements[i]=elem;
}删除
ElemType DeleteMax(MaxHead * head)
{if(IsEmpty(*head)){//判断堆是否为空cout<<"堆空!"<<endl;return -MAXELEM;}ElemType MaxElem=head->elements[1];//堆中第一个元素为最大值 保存用于返回ElemType temp=head->elements[(head->size)--];//将最后一个元素先放到第一个元素上，再做调整int parent,child;for(parent=1;parent*2<=head->size;parent=child){child=parent*2;if(child<head->size && head->elements[child+1]>head->elements[child])child++;//得到当前父节点的最大子节点的下标childif(temp>head->elements[child])//和父节点做比较break;elsehead->elements[parent]=head->elements[child];}head->elements[parent]=temp;return MaxElem;
}好，我们来附上具体的代码
//head.h
typedef int ElemType;
typedef struct MaxHead
{ElemType * elements;int size;int capacity;
}MaxHead;
MaxHead Create(int size);
bool IsFull(MaxHead head);
bool IsEmpty(MaxHead head);
void Insert(MaxHead * head,ElemType elem);
ElemType DeleteMax(MaxHead * head);
void Build(MaxHead *head,ElemType *data,int n);
void Printf(MaxHead head);
//head.cpp
#include "head.h"
#include <iostream>
#include <stdlib.h>
#define MAXELEM 99999
using namespace std;
MaxHead Create(int size)
{MaxHead H;H.capacity=size;H.elements=(ElemType*)malloc((size+1)*sizeof(ElemType));H.size=0;H.elements[0]=MAXELEM;return H;
}
bool IsFull(MaxHead head)
{return head.size==head.capacity;
}
bool IsEmpty(MaxHead head)
{return head.size==0;
}
void Insert(MaxHead * head,ElemType elem)
{if(IsFull(*head)){cout<<"堆满"<<endl;return ;}int i=++(head->size);for(;elem>head->elements[i/2];i/=2){head->elements[i]=head->elements[i/2];}head->elements[i]=elem;
}
ElemType DeleteMax(MaxHead * head)
{if(IsEmpty(*head)){cout<<"堆空!"<<endl;return -MAXELEM;}ElemType MaxElem=head->elements[1];ElemType temp=head->elements[(head->size)--];int parent,child;for(parent=1;parent*2<=head->size;parent=child){child=parent*2;if(child<head->size && head->elements[child+1]>head->elements[child])child++;if(temp>head->elements[child])break;elsehead->elements[parent]=head->elements[child];}head->elements[parent]=temp;return MaxElem;
}
void Build(MaxHead *head,ElemType *data,int n)
{for(int i=0;i<n;i++)//赋值head->elements[i+1]=data[i];head->size=n;int i=head->size/2;int parent,child;ElemType temp;for(;i>=1;i--){temp=head->elements[i];for(parent=i;parent*2<=head->size;parent=child){child=parent*2;if(child<head->size && head->elements[child+1]>head->elements[child])child++;if(temp>head->elements[child])break;elsehead->elements[parent]=head->elements[child];}head->elements[parent]=temp;}
}
void Printf(MaxHead head)
{for(int i=1;i<=head.size;i++){cout<<head.elements[i]<<" ";}cout<<endl;
}
//main.cpp
#include <iostream>
#include <stdlib.h>
#include "head.h"
using namespace std;
int main()
{int opt=1;MaxHead H;int size;ElemType * data;ElemType elem;while(opt!=5){puts("1-创建堆 2-插入");puts("3-删除 4-遍历 5-退出");cin>>opt;switch(opt){case 1:{puts("请设置堆的容量");cin>>size;H=Create(size);puts("请输入初始元素个数n");cin>>size;data=(ElemType*)malloc(size*sizeof(ElemType));for(int i=0;i<size;i++)cin>>data[i];Build(&H,data,size);break;}case 2:{puts("请输入元素");cin>>elem;Insert(&H,elem);break; }case 3:{elem=DeleteMax(&H);cout<<elem<<endl;break;}case 4:{Printf(H);break;}case 5:{opt=5;break;}default:{cout<<"输入有误！"<<endl;break;}}}return 0;
}
发布评论