网站建设费用什么意思搜狗友链交换

1. 堆的定义

堆（Heap）是一种特殊的树形数据结构，它满足以下性质：

• 堆是一个完全二叉树。
• 堆中每个节点的值都大于或等于（最大堆）或小于或等于（最小堆）其子节点的值。

1.1 最大堆

在最大堆中，父节点的值总是大于或等于子节点的值。

    10/  \9    8/ \  / \
7  6 5  4

1.2 最小堆

在最小堆中，父节点的值总是小于或等于子节点的值。

    1/ \2   3/ \ / \
4  5 6  7

2. 堆的表示方法

堆通常使用数组来表示，因为堆是完全二叉树，可以很方便地用数组存储。

2.1 数组表示法

• 父节点的索引为 i，则其左子节点的索引为 2*i + 1，右子节点的索引为 2*i + 2。
• 子节点的索引为 i，则其父节点的索引为 (i-1)/2。

3. 堆的基本操作

3.1 插入操作

插入新元素时，先将其放在堆的末尾，然后通过上滤（sift-up）操作将其移动到正确的位置。

#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 100typedef struct {int data[MAX_SIZE];int size;
} Heap;void initHeap(Heap* heap) {heap->size = 0;
}void siftUp(Heap* heap, int index) {int parent = (index - 1) / 2;while (index > 0 && heap->data[parent] < heap->data[index]) {int temp = heap->data[parent];heap->data[parent] = heap->data[index];heap->data[index] = temp;index = parent;parent = (index - 1) / 2;}
}void insert(Heap* heap, int value) {if (heap->size == MAX_SIZE) {printf("Heap overflow\n");return;}heap->data[heap->size] = value;siftUp(heap, heap->size);heap->size++;
}

3.2 删除操作

删除堆顶元素时，用堆的最后一个元素替换堆顶元素，然后通过下滤（sift-down）操作将其移动到正确的位置。

void siftDown(Heap* heap, int index) {int left = 2 * index + 1;int right = 2 * index + 2;int largest = index;if (left < heap->size && heap->data[left] > heap->data[largest]) {largest = left;}if (right < heap->size && heap->data[right] > heap->data[largest]) {largest = right;}if (largest != index) {int temp = heap->data[index];heap->data[index] = heap->data[largest];heap->data[largest] = temp;siftDown(heap, largest);}
}int deleteMax(Heap* heap) {if (heap->size == 0) {printf("Heap underflow\n");return -1;}int max = heap->data[0];heap->data[0] = heap->data[heap->size - 1];heap->size--;siftDown(heap, 0);return max;
}

3.3 堆排序

堆排序（Heap Sort）是一种利用堆这种数据结构所设计的排序算法。

void heapify(Heap* heap) {for (int i = (heap->size / 2) - 1; i >= 0; i--) {siftDown(heap, i);}
}void heapSort(int* array, int size) {Heap heap;initHeap(&heap);for (int i = 0; i < size; i++) {insert(&heap, array[i]);}heapify(&heap);for (int i = size - 1; i >= 0; i--) {array[i] = deleteMax(&heap);}
}

4. 堆的应用

4.1 优先队列

堆实现的优先队列可以在O(log n)时间内插入元素和删除最大（或最小）元素。

#include <stdio.h>
#include <stdlib.h>typedef struct {Heap heap;
} PriorityQueue;void initPriorityQueue(PriorityQueue* pq) {initHeap(&pq->heap);
}void enqueue(PriorityQueue* pq, int value) {insert(&pq->heap, value);
}int dequeue(PriorityQueue* pq) {return deleteMax(&pq->heap);
}

4.2 堆排序

堆排序是一种基于堆的数据结构的排序算法，时间复杂度为O(n log n)。

void heapSort(int* array, int size) {Heap heap;initHeap(&heap);for (int i = 0; i < size; i++) {insert(&heap, array[i]);}heapify(&heap);for (int i = size - 1; i >= 0; i--) {array[i] = deleteMax(&heap);}
}