最小堆插入元素和删除堆顶(无哨兵元素) (20分)
6-1 最小堆插入元素和删除堆顶(无哨兵元素) (20分)
对于给定的最小堆(优先队列),分别实现插入元素和删除堆顶的函数。
函数接口定义:
int insertIntoHeap(struct Heap* h, int x); // 向堆中插入元素x
int deleteMin(struct Heap* h, int* pElement); //将堆顶元素拷贝到pElement所指变量并删除堆顶元素
其中,h、x和pElement为参数,h是堆结构体指针,x是待插入元素的值,pElement指向的变量用于存放删除的堆顶元素。
堆结构体定义如下:
struct Heap{
int *data; // 堆元素存储空间指针,堆元素从data[1]开始存放,data[0]不使用,无哨兵元素
int capacity; // 堆容量
int size; // 堆元素数量
};
裁判测试程序样例:
#include <stdio.h>
#include <stdlib.h>
struct Heap{
int *data;
int capacity;
int size;
};
struct Heap* initHeap(int capacity){
// 初始化堆
struct Heap* h;
h = (struct Heap*)malloc(sizeof(struct Heap));
if(!h) return NULL;
h->data = (int*)malloc(sizeof(int)*capacity+1);
if(h->data == NULL){
free(h);
return NULL;
}
h->capacity = capacity;
h->size = 0;
return h;
};
void printHeap(struct Heap* h){
// 打印堆元素
/* 细节省略 */
}
int insertIntoHeap(struct Heap* h, int x);
int deleteMin(struct Heap* h, int* pElement);
int main(){
struct Heap *h;
int n;
scanf("%d", &n); // 输入堆容量
h = initHeap(n);
int op, x;
scanf("%d", &op);
while(op){
// 输入操作: -1表示删除 1表示插入 0表示结束
if(op == 1){
scanf("%d", &x);
printf("Insertion %s. ", insertIntoHeap(h, x) ? "succeeded" : "failed" );
printHeap(h);
}
else{
if (deleteMin(h, &x) ) printf("%d deleted. ", x);
else printf("Deletion failed. ");
printHeap(h);
}
scanf("%d", &op);
}
return 0;
}
/*你提交的代码将被嵌在这里 */
输入样例:
对于样例测试程序规定的输入格式:
3
1 10
1 20
1 5
1 40
-1
-1
-1
-1
0
输出样例:
样例测试程序的输出:
Insertion succeeded. 10,
Insertion succeeded. 10, 20,
Insertion succeeded. 5, 20, 10,
Insertion failed. 5, 20, 10,
5 deleted. 10, 20,
10 deleted. 20,
20 deleted.
Deletion failed.
int insertIntoHeap(struct Heap* h, int x){
if(h->size==h->capacity)
return 0;
int i;
i=++h->size;
for(;x<h->data[i/2];i/=2)
{
h->data[i]=h->data[i/2];
if (i/2 == 0) break;
}
h->data[i]=x;
return 1;
}
int deleteMin(struct Heap* h, int* pElement){
if(h->size==0)
return 0;
*pElement=h->data[1];
int temp=h->data[h->size--];
int parent,child;
for(parent=1;parent*2<=h->size;parent=child){
child=parent*2;
if((child!=h->size)&&(h->data[child]>h->data[child+1]))
child++;
if(temp<=h->data[child])
break;
else
h->data[parent]=h->data[child];
}
h->data[parent]=temp;
return 1;
}