算法导论_第六章_堆排序
对于堆排序，我就不着重介绍，
这是我写的另一篇介绍堆排序的文章：
http://blog.csdn.net/chudongfang2015/article/details/51173902
这里贴上代码：
#include<stdio.h>
#include<string.h>
#include<math.h>
int h[1000],n;
void swap(int x,int y);
void siftdown(int i);
void siftup(int i);
void creat();
int deletemax();
void print();
int main()
{
int i,num;
printf("please input the number of array:");
scanf("%d",&num);
for(i=1;i<=num;i++)
scanf("%d",&h[i]);
n=num;
creat();
//print();
for(i=1;i<=num;i++)
printf("%d ",deletemax());
return 0;
}
void swap(int x,int y)
{
int t;
t=h[x];
h[x]=h[y];
h[y]=t;
}
void siftdown(int i)
{
int t,flag=0;
while(i*2<=n&&flag==0)//t代表三个里面最小值
{
if(h[i*2]>h[i])
t=i;
else
t=i*2;
if(i*2+1<=n)
if(h[t]>h[i*2+1])
t=i*2+1;
if(t!=i)
{
swap(t,i);//交换
i=t;//赋值，继续判断
}
else //如果父节点不再大于子节点，则跳出循环
flag=1;
}
}
void shiftup(int i)
{
int t,flag=0;
if(i==1) return ;
while(i/2>=1&&flag==0)
{
if(h[i/2]>h[i])
{
t=i/2;
swap(i,t);
i=t;
}
else
flag=1;//父节点比子节点小
}
}
void creat()
{
int i;
for(i=n/2;i>=1;i--)
{
siftdown(i);
//print();
}
}
int deletemax()
{
int t;
t=h[1];
h[1]=h[n];
n--;
siftdown(1);
return t;
}
void print()
{
int i;
for(i=1;i<=n;i++)
printf("%d ",h[i]);
printf("\n");
}
堆排序的时间复杂度为O(n*lg(n))
每次维护堆为O(lg(n))
要进行n次维护，所以堆排序的时间复杂度为O(n*lg(n))
我在这里着重介绍队列优先：
优先队列是一种用来维护由一组元素构成的集合S的数据结构，其中的每一个元素都有一个相关的值，称为关键字，一个最大优先队列支持以下操作：
INSERT(S,x) 把X元素插入到集合S中
其时间复杂度为O(lg(n))，
MAXUMUM(S) 返回S中具有最大建字的元素
EXTRACT_MAX(S) 去掉并返回S中的最大键值
INCREASE_KEY(S,x,k) 将元素x的关键字征增加到k这里假设k的值不小于x的原关键字
其时间复杂度为O(lg(n))，因为其最大高度为lg(n)
这里的最大优先队列可以应用与共享计算机系统的作业调度。最小优先队列可以被用于
事件驱动的模拟器
下面上代码：
/*************************************************************************
> File Name: HEAP_SORT.cpp
> Author:chudongfang
> Mail:1149669942@qq.com
> Created Time: 2016年06月28日 星期二 19时00分47秒
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int h[1000],n;
void swap(int x,int y);
void siftdown(int i);
void siftup(int i);
void creat();
void print();
int EXTRACT_MAX();
int MAXIMUM();
void INSERT(int k);
void INCREASE_KEY(int x,int k);
int main()
{
int i,num=5;//初始化
for(i=5;i>=1;i--)
h[6-i]=i;
n=num;
creat();//创建堆
printf("MAXIMUM=%d\n",MAXIMUM());//输出有最大键值的元素
EXTRACT_MAX();//删除有最大键值的元素
for(i=1;i<=n;i++)
printf("%d ",h[i]);
printf("\n\n");
INCREASE_KEY(3,100);//增加3的关键字值到100
for(i=1;i<=n;i++)
printf("%d ",h[i]);
printf("\n\n");
INSERT(200);
for(i=1;i<=n;i++)
printf("%d ",h[i]);
return 0;
}
void swap(int x,int y)//交换
{
int t;
t=h[x];
h[x]=h[y];
h[y]=t;
}
void siftdown(int i)
{
int t,flag=0;
while(i*2<=n&&flag==0)//t代表三个里面最大值
{
if(h[i*2]<h[i])
t=i;
else
t=i*2;
if(i*2+1<=n)
if(h[t]<h[i*2+1])
t=i*2+1;
if(t!=i)
{
swap(t,i);//交换
i=t;//赋值，继续判断
}
else //如果父节点不再小于子节点，则跳出循环
flag=1;
}
}
void shiftup(int i)
{
int t,flag=0;
if(i==1) return ;
while(i/2>=1&&flag==0)
{
if(h[i/2]>h[i])
{
t=i/2;
swap(i,t);
i=t;
}
else
flag=1;//父节点比子节点小
}
}
void creat()//创建堆
{
int i;
for(i=n/2;i>=1;i--)
{
siftdown(i);
//print();
}
}
int EXTRACT_MAX()
{
int t;
t=h[1];
h[1]=h[n];
n--;
siftdown(1);
return t;
}
void print()
{
int i;
for(i=1;i<=n;i++)
printf("%d ",h[i]);
printf("\n");
}
int MAXIMUM()
{
return h[1];
}
void INCREASE_KEY(int x,int k)
{
if(k<h[x])
{
printf("new key is smaller than current key!");
return ;
}
h[x]=k;
while(x>1&&h[x/2]<h[x])
{
swap(x,x/2);
x=x/2;
}
return ;
}
void INSERT(int k)//实现插入
{
n++;//增加元素
h[n]=-INF;
INCREASE_KEY(n,k);//把其值增加到k
}