首页 > 代码库 > 二叉堆部分练习
二叉堆部分练习
本练习主要做了几个工作：
1.给定一个数组来初始化二叉堆，第一种方法是通过不断插入，时间复杂度是O(nlgn)，第二种方法是先把数组填入二叉堆，再从下标为H->SIZE/2的节点开始下滤，这是因为只有下标小于为H->SIZE/2才有孩子，从而可以用线性时间完成二叉堆的初始化。
2.二叉堆的下滤和上滤，对二叉堆关键字的操作诸如删除最小，增加某关键字值，减少某关键字值等会可能改变堆性质的操作，必须用上滤和下滤来保证二叉堆的性质，比如增加了某关键字的值，该关键字可能往下走，因此对该节点采用下滤，与之相反，减少时则要上滤。
3.删除操作是把要删除关键字的位置先求出来，用二叉树最后一个数字来覆盖这个位置的值，并使堆的大小减1，此时要比较要删除的值与该位置新值，根据大小关系来采用上滤或下滤。
4.给定一个x，用O(K)的时间求出小于x的关键字，主要用了层序遍历的思想，从上往下一层层地走，遇到比x小的把它儿子入栈，循环至栈空。
5.用至多3N/4的时间找出任意一个关键字x的位置，主要是先比较倒数第二层的节点，看x和这层节点的关系，若x大于这层所有的节点，这只需要检查所有叶节点，而叶节点的数量不会超过N/2，倒数第二层的节点不会超过N/4，故此时总的比较次数不会超过3N/4。若x小于这层所有的节点，则只需要检查剩下的N/2个节点即可，满足题意。
// youxianduilie_lianxi.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<iostream>
#include<stack>
using namespace std;
struct HeapStruct;
typedef struct HeapStruct *PriorityQueue;
#define MinData -65536
#define notExist -1
struct HeapStruct
{
int Capacity;
int Size;
int *Elements;
};
PriorityQueue Initialize(int MaxElement) //初始化堆
{
PriorityQueue H = (PriorityQueue)malloc(sizeof(HeapStruct)); //1.申请一个堆
if (H == NULL) cout << "out of space";
H->Elements = (int *)malloc(sizeof(int)*(MaxElement + 1)); //2.申请一片地址空间用于存放数组
if (H->Elements == NULL) cout << "out of space";
H->Capacity = MaxElement; //3.其余值初始化
H->Size = 0;
H->Elements[0] = MinData;
return H;
}
bool isFull(PriorityQueue H)
{
if (H->Size >= H->Capacity)
return 1;
else
return 0;
}
void Insert(int x, PriorityQueue H)
{
int i;
if (isFull(H)) //1.先检查堆有没有满
{
cout << "Priority queue is full";
return;
}
for (i = ++H->Size; H->Elements[i / 2] > x; i /= 2) //循环，在Size+1的位置创建一个空穴，
H->Elements[i] = H->Elements[i / 2]; //通过x不断与其父节点比较,空穴不断上移，直到父节点小于X；
H->Elements[i] = x; //此时i的值就是x所插入的位置。
}
PriorityQueue InitByInsert(int MaxElement,const int Given[],int num)
{
PriorityQueue H = Initialize(MaxElement);
for (int i = 0; i < num; i++)
Insert(Given[i], H);
return H;
}
void PercDown(PriorityQueue H, int i) //下滤操作
{
int Tmp;
int child;
for (Tmp = H->Elements[i]; 2 * i <= H->Size; i = child)
{
child = 2 * i;
if (H->Elements[child + 1] && H->Elements[child + 1] < H->Elements[child]) //第一次比较，如果右儿子存在而且比较小
child += 1;
if (Tmp > H->Elements[child]) //i位原来的值是Tmp，当儿子比他还小时就下滤，循环直到儿子都比他大
H->Elements[i] = H->Elements[child]; //每次这样赋值后，child位会被空出来，结合循环i=child
else
break;
}
H->Elements[i] = Tmp;
}
void PercUp(PriorityQueue H, int i) //上滤操作跟下滤操作基本是对偶的
{
int Tmp;
int parent;
for (Tmp = H->Elements[i]; i > 0; i = parent)
{
parent = i >> 1;
if (Tmp < H->Elements[parent])
H->Elements[i] = H->Elements[parent];
else
break;
}
H->Elements[i] = Tmp;
}
PriorityQueue InitByGiven(int MaxElement, const int Given[], int num)
{
PriorityQueue H = Initialize(MaxElement);
for (int i = 1; i <= num; i++)
H->Elements[i] = Given[i - 1];
H->Size = num;
/*下滤的循环
for (int i = H->Size / 2; i > 0; i--) //二叉树节点的数量最多为 H->Size / 2，比如一个满二叉树有一半是叶子
PercDown(H, i);
*/
//上滤的循环
for(int i=2;i<=H->Size;i++)
PercUp(H, i);
return H;
}
int DeleteMin(PriorityQueue H) //删除并返回最小值
{
int i, child;
int minElement, LastElement;
if (H->Size==0) { //先检查是否为空
cout << "is Empty";
return H->Elements[0];
}
minElement = H->Elements[1]; //最小的在堆顶
LastElement = H->Elements[H->Size--]; //删除后Size-1；
H->Elements[1] = LastElement; //堆顶的元素取走以后，留下一个空穴，把堆的最后一个元素放在堆顶上，对其进行下滤即可。
PercDown(H, 1);
return minElement;
}
void Delete(PriorityQueue H, int key) //直接删除
{
int i;
for (i = 1; i <= H->Size; i++) //先找到位置
if (H->Elements[i] == key) break;
H->Elements[i]= H->Elements[H->Size--]; //用最后一个元素覆盖要删除位置的值，再下滤
PercDown(H, i);
}
void rewrite(int oldkey, int newkey, PriorityQueue H)
{
int i;
for (i = 1; i <= H->Size; i++) //先找到位置
if (H->Elements[i] == oldkey) break;
H->Elements[i] = newkey;
if(newkey>oldkey) //比较新旧值，比旧值大的话就要下滤，相当于IncreaseKey操作，比旧值小的话就要上滤，相当于DecreaseKey操作
PercDown(H, i);
else
PercUp(H, i);
}
void lessThan(int x, PriorityQueue H) //用O(K)时间打印出堆中小于x的数
{
if (H->Elements[1] >= x) cout << H->Elements[0];
else
{
int i = 1;
stack<int> reme; //类似层序遍历，当父节点的值大于x时，就不再去检查子节点
reme.push(i);
while (!reme.empty())
{
if (H->Elements[reme.top()] < x)
{
i = reme.top();
cout << H->Elements[reme.top()]<<‘\t‘;
reme.pop();
if (2 * i <= H->Size) reme.push(2 * i);
if (2 * i+1 <= H->Size) reme.push(2 * i+1);
}
else
reme.pop();
}
}
}
int quickFind(PriorityQueue H, int x)
{
int left, right;
for (int i = H->Size / 2; i >= H->Size / 4; i--) //此循环用于检查叶节点的上一层
if (H->Elements[i] < x)
{
left = 2 * i;
right = 2 * i + 1;
if (left <= H->Size&&H->Elements[left] == x)
return left;
if (right <= H->Size&&H->Elements[right] == x)
return right;
}
for (int i = H->Size / 2; i > 0; i--) //如果上面在叶节点检查出来了就不会执这个循环
{
if (x == H->Elements[i])
return i;
}
return notExist;
}
void print(PriorityQueue H)
{
for (int i = 1; i <= H->Size; i++)
cout << H->Elements[i] << ‘\t‘;
cout << endl;
}
int main()
{
int Given[] = { 10,12,1,14,6,5,8,15,3,9,7,4,11,13,2 };
//PriorityQueue H=InitByInsert(100, Given, 15);
PriorityQueue H = InitByGiven(100, Given, 15);
print(H);
//lessThan(6, H);
cout << quickFind(H, 12);
//int min = DeleteMin(H);
//cout << min << endl;
//print(H);
//Delete(H, 3);
//print(H);
//rewrite(2,77,H);
//print(H);
while (1);
return 0;
}
二叉堆部分练习
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。