您现在的位置是：网站首页>技术百科技术百科

数据结构之堆（Heap）

小大寒2024-01-01[技术百科]博学多闻

数据结构之堆（Heap）堆是一种特殊的完全二叉树，满足堆的性质：父节点的值大于或小于子节点的值。根据堆的性质分为最大堆和最小堆。堆常用于实现优先队列、快速选择算法等。

数据结构之堆（Heap）

1. 基础概念

1.1 堆的定义

堆是一种完全二叉树，常见的类型有最大堆和最小堆。最大堆的父节点的值总是不小于其子节点的值，而最小堆的父节点的值总是不大于其子节点的值。堆是一种偏序的树形结构，用于快速获取最大值或最小值。

1.2 堆的特点

完全二叉树：除了最后一层外，其他层的节点都被填满。
堆的性质：最大堆中每个父节点的值都大于等于其子节点的值，最小堆中每个父节点的值都小于等于其子节点的值。
用于高效的插入、删除最大值（或最小值）操作。
堆的实现通常使用数组，父节点的索引为i时，其左子节点索引为2i+1，右子节点索引为2i+2。

1.3 使用场景

优先队列：堆常用于实现优先队列，能够高效地进行元素的插入和删除操作。
堆排序：堆可以用来进行排序，堆排序的时间复杂度为O(n log n)。
图的最短路径算法：在Dijkstra和Prim算法中，堆用于快速选取最短路径或最小生成树中的节点。

2. 实现与操作

2.1 核心操作实现

堆的核心操作包括构建堆、插入元素、删除最大/最小元素以及堆化操作。以下是用C语言实现最大堆的代码：

        #include <stdio.h>
        #define MAX 100
        
        // 堆结构体
        typedef struct {
            int data[MAX];
            int size;
        } Heap;
        
        // 创建堆
        void initHeap(Heap* heap) {
            heap->size = 0;
        }
        
        // 插入元素
        void insert(Heap* heap, int value) {
            int i = heap->size++;
            heap->data[i] = value;
        
            // 上浮操作，保持堆的性质
            while (i > 0 && heap->data[i] > heap->data[(i - 1) / 2]) {
                int temp = heap->data[i];
                heap->data[i] = heap->data[(i - 1) / 2];
                heap->data[(i - 1) / 2] = temp;
                i = (i - 1) / 2;
            }
        }
        
        // 删除最大元素
        int deleteMax(Heap* heap) {
            if (heap->size == 0) {
                printf("堆为空!\n");
                return -1;
            }
            int max = heap->data[0];
            heap->data[0] = heap->data[--heap->size];
        
            // 下沉操作，保持堆的性质
            int i = 0;
            while (2 * i + 1 < heap->size) {
                int left = 2 * i + 1;
                int right = 2 * i + 2;
                int largest = i;
        
                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 == i) break;
        
                int temp = heap->data[i];
                heap->data[i] = heap->data[largest];
                heap->data[largest] = temp;
                i = largest;
            }
        
            return max;
        }
        
        int main() {
            Heap heap;
            initHeap(&heap);
        
            insert(&heap, 10);
            insert(&heap, 20);
            insert(&heap, 5);
            insert(&heap, 15);
        
            printf("删除最大值: %d\n", deleteMax(&heap));
            printf("删除最大值: %d\n", deleteMax(&heap));
        
            return 0;
        }
        </stdio.h>

2.2 代码详解

initHeap: 初始化堆，设置堆的大小为0。
insert: 插入新元素，并通过上浮操作保持堆的性质。
deleteMax: 删除堆顶元素（最大值），并通过下沉操作重新调整堆。

3. 时间与空间复杂度分析

3.1 时间复杂度

插入操作：每次插入时，元素可能需要通过上浮操作调整堆的位置，时间复杂度为O(log n)。
删除最大值操作：每次删除堆顶元素后，堆需要通过下沉操作恢复堆的性质，时间复杂度为O(log n)。
堆化操作（构建堆）：从最后一个非叶子节点开始调整堆，时间复杂度为O(n)。

3.2 空间复杂度

堆的空间复杂度为O(n)，其中n是堆中元素的个数。堆通常使用数组实现，不需要额外的指针空间。

4. 优缺点与局限性

4.1 优点

堆的插入、删除操作的时间复杂度为O(log n)，较为高效。
堆非常适合用于优先队列和实时计算最大/最小值。

4.2 缺点与局限性

堆的插入和删除操作时间复杂度为O(log n)，但无法进行任意位置的访问。
堆不支持按顺序访问元素，无法实现类似排序数组的线性遍历。

5. 常见应用场景

5.1 实际应用

堆常用于解决Top-K问题，如寻找数组中的K个最大或最小值。以下是一个解决Top-K问题的代码示例：

        #include <stdio.h>
        #include <stdlib.h>
        
        void topK(int* arr, int n, int k) {
            Heap heap;
            initHeap(&heap);
        
            for (int i = 0; i < n; i++) {
                if (heap.size < k) {
                    insert(&heap, arr[i]);
                } else if (arr[i] > heap.data[0]) {
                    deleteMax(&heap);
                    insert(&heap, arr[i]);
                }
            }
        
            printf("Top %d elements: ", k);
            for (int i = 0; i < k; i++) {
                printf("%d ", heap.data[i]);
            }
            printf("\n");
        }
        
        int main() {
            int arr[] = {1, 5, 2, 8, 9, 3, 4};
            int n = sizeof(arr) / sizeof(arr[0]);
            int k = 3;
            topK(arr, n, k);
        
            return 0;
        }
        </stdlib.h></stdio.h>