c语言如何构建小顶堆
时间: 2024-06-19 15:03:52 浏览: 14
在 C 语言中构建小顶堆可以通过以下几个步骤完成:
1. 定义一个结构体来表示堆,包括堆的大小和堆的数组元素。
```
typedef struct {
int *arr; // 堆的数组元素
int size; // 堆的大小
} MinHeap;
```
2. 实现交换函数 swap,用于交换堆中两个元素的位置。
```
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
```
3. 实现一个向下调整函数 siftDown,用于将一个元素向下调整到合适的位置,以维护堆的性质。
```
void siftDown(int *arr, int start, int end) {
int parent = start;
int child = parent * 2 + 1;
while (child <= end) {
if (child + 1 <= end && arr[child] > arr[child + 1]) {
child++;
}
if (arr[parent] <= arr[child]) {
break;
} else {
swap(&arr[parent], &arr[child]);
parent = child;
child = parent * 2 + 1;
}
}
}
```
4. 实现一个建堆函数 buildHeap,用于将一个数组构建成小顶堆。
```
void buildHeap(MinHeap *heap) {
int i;
for (i = heap->size / 2; i >= 0; i--) {
siftDown(heap->arr, i, heap->size - 1);
}
}
```
5. 实现一个弹出堆顶元素函数 pop,用于弹出堆顶元素,并重新调整堆。
```
int pop(MinHeap *heap) {
int top = heap->arr;
heap->arr = heap->arr[heap->size - 1];
heap->size--;
siftDown(heap->arr, 0, heap->size - 1);
return top;
}
```
6. 最后,我们可以按照以下步骤来构建一个小顶堆:
```
int main() {
int arr[] = {10, 20, 30, 40, 50, 60, 70};
int n = sizeof(arr) / sizeof(arr);
MinHeap heap = {arr, n};
buildHeap(&heap);
// 弹出堆顶元素
printf("%d ", pop(&heap));
return 0;
}
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](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)