Last active
March 26, 2019 07:59
-
-
Save tamarous/3e219c82d9b642171483fe12eb4bd01e to your computer and use it in GitHub Desktop.
二叉堆的插入和删除最小值操作
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
thanks.