用C++代码实现最小最大堆
时间: 2023-11-14 11:15:01 浏览: 58
可以通过下面的代码实现最小最大堆:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_HEAP_SIZE 100
typedef struct Heap {
int* data;
int size;
} Heap;
Heap* create_heap()
{
Heap* heap = (Heap*)malloc(sizeof(Heap));
heap->data = (int*)malloc(sizeof(int) * MAX_HEAP_SIZE);
heap->size = 0;
return heap;
}
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void down_adjust(Heap* heap, int index, int is_min_heap)
{
int left = index * 2 + 1;
int right = index * 2 + 2;
int maxmin = index;
if (is_min_heap) {
if (left < heap->size && heap->data[left] < heap->data[maxmin])
maxmin = left;
if (right < heap->size && heap->data[right] < heap->data[maxmin])
maxmin = right;
} else {
if (left < heap->size && heap->data[left] > heap->data[maxmin])
maxmin = left;
if (right < heap->size && heap->data[right] > heap->data[maxmin])
maxmin = right;
}
if (maxmin != index) {
swap(&heap->data[maxmin], &heap->data[index]);
down_adjust(heap, maxmin, is_min_heap);
}
}
void up_adjust(Heap* heap, int index, int is_min_heap)
{
if (index == 0) return;
int parent = (index - 1) / 2;
if (is_min_heap) {
if (heap->data[index] < heap->data[parent]) {
swap(&heap->data[index], &heap->data[parent]);
up_adjust(heap, parent, is_min_heap);
}
} else {
if (heap->data[index] > heap->data[parent]) {
swap(&heap->data[index], &heap->data[parent]);
up_adjust(heap, parent, is_min_heap);
}
}
}
void insert(Heap* heap, int value, int is_min_heap)
{
if (heap->size == MAX_HEAP_SIZE) {
printf("Heap is full!\n");
return;
}
heap->data[heap->size] = value;
heap->size++;
up_adjust(heap, heap->size - 1, is_min_heap);
}
void remove_heap(Heap* heap, int value, int is_min_heap)
{
if (heap->size == 0) {
printf("Heap is empty!\n");
return;
}
int i;
for (i = 0; i < heap->size; i++) {
if (heap->data[i] == value)
break;
}
if (i == heap->size) {
printf("Element not found in heap!\n");
return;
}
heap->data[i] = heap->data[heap->size - 1];
heap->size--;
down_adjust(heap, i, is_min_heap);
}
void print_heap(Heap* heap)
{
int i;
for (i = 0; i < heap->size; i++)
printf("%d ", heap->data[i]);
printf("\n");
}
int main()
{
Heap* min_heap = create_heap();
Heap* max_heap = create_heap();
insert(min_heap, 5, 1);
insert(min_heap, 6, 1);
insert(min_heap, 4, 1);
insert(min_heap, 2, 1);
insert(min_heap, 3, 1);
insert(max_heap, 5, 0);
insert(max_heap, 6, 0);
insert(max_heap, 4, 0);
insert(max_heap, 2, 0);
insert(max_heap, 3, 0);
printf("Min heap: ");
print_heap(min_heap);
printf("Max heap: ");
print_heap(max_heap);
remove_heap(min_heap, 4, 1);
remove_heap(max_heap, 4, 0);
printf("Min heap after removing 4: ");
print_heap(min_heap);
printf("Max heap after removing 4: ");
print_heap(max_heap);
return 0;
}
```
这段代码实现了最小最大堆的基本功能,包括创建堆、插入元素、删除元素和打印堆。其中,指定 is_min_heap 参数可以创建最小堆或最大堆。注意,在删除元素时,需要先将要删除的元素与堆的最后一个元素交换位置,然后再进行下沉操作,以保证堆的完整性。