用c代码解释堆
时间: 2023-12-16 14:06:24 浏览: 30
下面是使用 C 语言实现一个小根堆的例子,实现了堆的插入和弹出操作:
```c
#include <stdio.h>
#include <stdlib.h>
#define HEAP_SIZE 100
typedef struct {
int *arr; // 堆的数组
int size; // 堆中元素的个数
int capacity; // 堆的容量
} MinHeap;
// 初始化堆
void init_heap(MinHeap *heap, int capacity) {
heap->arr = (int *)malloc(sizeof(int) * capacity);
heap->size = 0;
heap->capacity = capacity;
}
// 插入元素
void push(MinHeap *heap, int val) {
if (heap->size >= heap->capacity) {
return;
}
heap->arr[heap->size] = val;
int idx = heap->size;
while (idx > 0) {
int parent_idx = (idx - 1) / 2;
if (heap->arr[parent_idx] > heap->arr[idx]) {
int tmp = heap->arr[parent_idx];
heap->arr[parent_idx] = heap->arr[idx];
heap->arr[idx] = tmp;
idx = parent_idx;
} else {
break;
}
}
heap->size++;
}
// 弹出堆顶元素
int pop(MinHeap *heap) {
if (heap->size == 0) {
return -1;
}
int root = heap->arr[0];
heap->size--;
heap->arr[0] = heap->arr[heap->size];
int idx = 0;
while (idx < heap->size) {
int left_idx = idx * 2 + 1;
int right_idx = idx * 2 + 2;
int min_idx = idx;
if (left_idx < heap->size && heap->arr[left_idx] < heap->arr[min_idx]) {
min_idx = left_idx;
}
if (right_idx < heap->size && heap->arr[right_idx] < heap->arr[min_idx]) {
min_idx = right_idx;
}
if (min_idx != idx) {
int tmp = heap->arr[min_idx];
heap->arr[min_idx] = heap->arr[idx];
heap->arr[idx] = tmp;
idx = min_idx;
} else {
break;
}
}
return root;
}
int main() {
MinHeap heap;
init_heap(&heap, HEAP_SIZE);
push(&heap, 3);
push(&heap, 1);
push(&heap, 4);
push(&heap, 2);
push(&heap, 5);
while (heap.size > 0) {
printf("%d ", pop(&heap));
}
return 0;
}
```
这里使用结构体来表示堆,包含堆的数组、元素个数和容量。插入时将元素添加到数组尾部,然后将元素与其父节点进行比较,如果父节点较大则交换两个节点,直到满足小根堆的性质。
弹出时将堆顶元素取出,将数组最后一个元素放到堆顶,然后将堆顶元素与其左右子节点中较小的那个进行比较,如果子节点较小则交换两个节点,直到满足小根堆的性质。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)