Skip to content

Instantly share code, notes, and snippets.

@tamarous
Last active March 26, 2019 07:59
Show Gist options
  • Save tamarous/3e219c82d9b642171483fe12eb4bd01e to your computer and use it in GitHub Desktop.
Save tamarous/3e219c82d9b642171483fe12eb4bd01e to your computer and use it in GitHub Desktop.
二叉堆的插入和删除最小值操作
#include <stdio.h>
#include <stdlib.h>
#define MinPQSize 5
#define MinData -10000
struct HeapStruct;
typedef struct HeapStruct *priorityQueue;
typedef int ElementType;
priorityQueue initialize(int elementsNum);
void destroy(priorityQueue H);
void makeEmpty(priorityQueue H);
void insert(ElementType x, priorityQueue H);
ElementType deleteMin(priorityQueue H);
ElementType findMin(priorityQueue H);
int isEmtpy(priorityQueue H);
int isFull(priorityQueue H);
struct HeapStruct {
int capacity;
int size;
ElementType *elements;
};
priorityQueue initialize(int elementsNum)
{
priorityQueue H;
if( elementsNum < MinPQSize) {
printf("size is too small...\n");
}
H = (priorityQueue)malloc(sizeof(struct HeapStruct));
if (H == NULL) {
printf("failed to malloc...\n");
}
H->elements = (ElementType *)malloc(sizeof(ElementType) * elementsNum);
if (H->elements == NULL) {
printf("failed to malloc...\n");
}
H->capacity = elementsNum;
H->size = 0;
H->elements[0] = MinData;
return H;
}
void insert(ElementType x, priorityQueue H)
{
int i ;
if( isFull(H)) {
printf("priority queue is full...\n");
return;
}
for(i == ++H->size;H->elements[i/2] > x; i /= 2 ) {
H->elements[i] = H->elements[i/2];
}
H->elements[i] = x;
}
ElementType deleteMin(priorityQueue H)
{
int i,child;
ElementType min, last;
if( isEmpty(H)) {
printf("priority queue is emtpy...\n");
return;
}
min = H->elements[1];
last = H->elements[H->size--];
for(i = 1;i * 2 <= H->size;i++) {
child = i*2;
if(child != H->size && H->elements[child+1] < H->elements[child]) {
child++;
}
if(last > H->elements[child]) {
H->elements[i] = H->elements[child];
} else {
break;
}
}
H->elements[i] = last;
return min;
}
@xiaomin-D
Copy link

thanks.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment