以下是一种可能的ADT MAXHEAP的C语言实现示例:
#include
#include
#define MAX_SIZE 100
typedef struct {
int* array;
int size;
int capacity;
} MaxHeap;
MaxHeap* createMaxHeap(int capacity) {
MaxHeap* heap = (MaxHeap*)malloc(sizeof(MaxHeap));
heap->array = (int*)malloc(sizeof(int) * (capacity + 1));
heap->size = 0;
heap->capacity = capacity;
return heap;
}
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
void insert(MaxHeap* heap, int value) {
if (heap->size == heap->capacity) {
printf("Heap is full\n");
return;
}
heap->size++;
int i = heap->size;
heap->array[i] = value;
while (i > 1 && heap->array[i/2] < heap->array[i]) {
swap(&heap->array[i/2], &heap->array[i]);
i = i/2;
}
}
void heapify(MaxHeap* heap, int i) {
int largest = i;
int left = 2 * i;
int right = 2 * i + 1;
if (left <= heap->size && heap->array[left] > heap->array[largest]) {
largest = left;
}
if (right <= heap->size && heap->array[right] > heap->array[largest]) {
largest = right;
}
if (largest != i) {
swap(&heap->array[i], &heap->array[largest]);
heapify(heap, largest);
}
}
int extractMax(MaxHeap* heap) {
if (heap->size == 0) {
printf("Heap is empty\n");
return -1;
}
int max = heap->array[1];
heap->array[1] = heap->array[heap->size];
heap->size--;
heapify(heap, 1);
return max;
}
void printHeap(MaxHeap* heap) {
printf("Heap: ");
for (int i = 1; i <= heap->size; i++) {
printf("%d ", heap->array[i]);
}
printf("\n");
}
int main() {
MaxHeap* heap = createMaxHeap(MAX_SIZE);
insert(heap, 5);
insert(heap, 10);
insert(heap, 8);
insert(heap, 3);
insert(heap, 6);
printHeap(heap);
int max = extractMax(heap);
printf("Extracted max: %d\n", max);
printHeap(heap);
free(heap->array);
free(heap);
return 0;
}
这是一个基本的最大堆(Max Heap)的实现,其中包含了一些常用的操作,如插入、堆化和提取最大值。请注意,此实现假设数组中的索引从1开始,而不是从0开始。
上一篇:ADT JSON序列化/反序列化