devbox
菜鸟追梦旅行
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构的堆（c语言版）

作者：菜鸟追梦旅行 | 2024-05-15 16:52:07

赞

踩

数据结构的堆（c语言版）

一.堆的概念

1.堆的基本概念

在计算机科学中，堆是一种特殊的数据结构，通常用于实现优先队列和动态分配内存。

2.堆的特征

堆是一个完全二叉树，它具有以下两个主要特性：

  1. 堆序性：对于最大堆，在堆中的任意节点i，其父节点的值大于等于节点i的值；对于最小堆，在堆中的任意节点i，其父节点的值小于等于节点i的值。这意味着在最大堆中，根节点是堆中最大的元素；在最小堆中，根节点是堆中最小的元素。

  2. 完全二叉树性质：除了最底层外，堆的其他层都是满的，并且最底层的节点集中在左侧。

3.堆的性质

根据堆序性质，我们可以高效地找到堆中的最大（最小）元素。这使得堆非常适用于解决一些需要高效获取最大（最小）元素的问题，例如优先队列和排序算法（如堆排序）。

堆可以用数组来实现，其中父节点和子节点之间的关系可以通过索引计算得出。通常，堆的插入和删除操作会触发堆的调整，以维持堆序性质。

需要注意的是，堆和操作系统中的堆内存分配是不同的概念。在操作系统中，堆内存指的是动态分配的内存区域，而在数据结构中，堆是一种数据结构。

4.堆的优缺点

优点：

  1. 高效的插入和删除操作：在堆中，插入和删除元素的时间复杂度为O(log n)，其中n是堆中元素的个数。这是由于堆的调整过程只需要对树的高度进行操作，堆的高度通常比较小。

  2. 快速获取最大（最小）元素：在最大堆中，根节点是堆中的最大元素；在最小堆中，根节点是堆中的最小元素。因此，可以在O(1)的时间复杂度内获取最大（最小）元素。

  3. 实现优先队列：堆常用于实现优先队列，其中元素按照优先级进行排序。优先队列可以在O(1)的时间复杂度内获取最高优先级的元素，并且在O(log n)的时间复杂度内插入和删除元素。

缺点：

  1. 不支持快速查找：堆并不提供快速查找指定元素的功能。如果需要在堆中进行查找操作，时间复杂度为O(n)，需要遍历整个堆。

  2. 内存空间的浪费：堆使用数组来存储元素，如果事先不知道元素的个数，需要预分配一个较大的数组空间。这可能会导致内存空间的浪费。

  3. 不稳定性：堆排序算法是一种不稳定的排序算法。在排序过程中，相等元素的相对顺序可能会改变。

二.堆的功能

  1. 插入元素：向堆中插入一个新元素。插入操作会根据堆的特性进行调整，以保持堆的性质。

  2. 删除最大（最小）元素：从堆中删除并返回最大（最小）元素。删除操作会将堆的最后一个元素移到堆顶，并根据堆的特性进行调整，以保持堆的性质。

  3. 获取最大（最小）元素：返回堆中的最大（最小）元素，而不删除它。获取操作只是简单地返回堆的根节点的值。

  4. 堆排序：使用堆进行排序。堆排序是一种基于堆的排序算法，它利用堆的性质进行排序操作。

  5. 构建堆：将一个无序的数组转换为一个堆。构建堆的过程会进行堆调整，以满足堆的性质。

  6. 堆化：对一个已有的堆进行调整，以满足堆的性质。堆化可以通过自上而下或自下而上的方式进行。

  7. 堆的合并：将两个堆合并为一个堆。堆的合并操作通常用于合并多个优先队列。

  8. 查找元素：在堆中查找指定元素。由于堆并不提供快速查找功能，查找操作需要遍历整个堆，时间复杂度为O(n)。

三.堆的代码实现

1.堆的定义

创建一个结构体，其中成员如下：

  • array：一个指向整型数组的指针，用于存储堆中的元素。
  • capacity：一个整数，表示堆的容量，即 array 数组的最大长度。
  • size：一个整数，表示当前堆中的元素个数，即 array 数组中实际存储的元素数量。
  1. typedef struct {
  2.     int* array;     // 存储堆元素的数组
  3.     int capacity;   // 堆的容量
  4.     int size;       // 堆中当前元素的个数
  5. } Heap;

2.创建堆

创建堆。该函数接受一个整数参数 capacity，表示堆的容量。它会分配堆所需的内存，并返回指向堆结构的指针。

  1. // 创建堆
  2. Heap* createHeap(int capacity) {
  3.     Heap* heap = (Heap*)malloc(sizeof(Heap));
  4.     heap->array = (int*)malloc(sizeof(int) * capacity);
  5.     heap->capacity = capacity;
  6.     heap->size = 0;
  7.     return heap;
  8. }

3.交换两个数值

交换两个元素的值。该函数接受两个整型指针作为参数，通过引用交换指针所指向的两个整数的值。

  1. // 交换两个元素
  2. void swap(int* a, int* b) {
  3.     int temp = *a;
  4.     *a = *b;
  5.     *b = temp;
  6. }

4.入堆

向堆中插入元素。该函数接受一个指向堆结构的指针 heap 和要插入的整数值 value。它将元素插入到堆的最后位置，并通过自上而下的调整操作，保持堆的性质。

  1. // 向堆中插入元素
  2. void insert(Heap* heap, int value) {
  3.     if (heap->size == heap->capacity) {
  4.         printf("堆已满，无法插入新元素。\n");
  5.         return;
  6.     }
  7.     
  8.     // 将新元素插入到堆的最后位置
  9.     heap->array[heap->size] = value;
  10.     
  11.     int currentIndex = heap->size;
  12.     int parentIndex = (currentIndex - 1) / 2;
  13.     
  14.     // 自下而上调整堆结构
  15.     while (currentIndex > 0 && heap->array[currentIndex] > heap->array[parentIndex]) {
  16.         swap(&heap->array[currentIndex], &heap->array[parentIndex]);
  17.         currentIndex = parentIndex;
  18.         parentIndex = (currentIndex - 1) / 2;
  19.     }
  20.     
  21.     heap->size++;
  22. }

5.出堆

从堆中删除并返回最大元素。该函数接受一个指向堆结构的指针 heap。它将堆顶元素（最大元素）删除，并将最后一个元素移到堆顶，然后通过自上而下的调整操作，保持堆的性质。

  1. // 从堆中删除并返回最大元素
  2. int deleteMax(Heap* heap) {
  3.     if (heap->size == 0) {
  4.         printf("堆为空，无法删除元素。\n");
  5.         return -1;
  6.     }
  7.     
  8.     int maxValue = heap->array[0];
  9.     
  10.     // 将最后一个元素移到堆顶
  11.     heap->array[0] = heap->array[heap->size - 1];
  12.     heap->size--;
  13.     
  14.     int currentIndex = 0;
  15.     int leftChildIndex = 2 * currentIndex + 1;
  16.     int rightChildIndex = 2 * currentIndex + 2;
  17.     
  18.     // 自上而下调整堆结构
  19.     while (1) {
  20.         int maxIndex = currentIndex;
  21.         
  22.         // 与左子节点比较
  23.         if (leftChildIndex < heap->size && heap->array[leftChildIndex] > heap->array[maxIndex]) {
  24.             maxIndex = leftChildIndex;
  25.         }
  26.         
  27.         // 与右子节点比较
  28.         if (rightChildIndex < heap->size && heap->array[rightChildIndex] > heap->array[maxIndex]) {
  29.             maxIndex = rightChildIndex;
  30.         }
  31.         
  32.         // 如果当前节点已经是最大值，则堆已调整完毕
  33.         if (maxIndex == currentIndex) {
  34.             break;
  35.         }
  36.         
  37.         // 否则，交换当前节点与最大子节点的位置
  38.         swap(&heap->array[currentIndex], &heap->array[maxIndex]);
  39.         currentIndex = maxIndex;
  40.         leftChildIndex = 2 * currentIndex + 1;
  41.         rightChildIndex = 2 * currentIndex + 2;
  42.     }
  43.     
  44.     return maxValue;
  45. }

6.打印堆

打印堆元素。该函数接受一个指向堆结构的指针 heap。它会遍历堆中的元素，并将它们打印出来。

  1. // 打印堆元素
  2. void printHeap(Heap* heap) {
  3.     printf("堆元素：");
  4.     for (int i = 0; i < heap->size; i++) {
  5.         printf("%d ", heap->array[i]);
  6.     }
  7.     printf("\n");
  8. }

7.销毁堆

释放堆内存。该函数接受一个指向堆结构的指针 heap。它会释放堆所占用的内存，防止内存泄漏。

  1. // 释放堆内存
  2. void destroyHeap(Heap* heap) {
  3.     free(heap->array);
  4.     free(heap);
  5. }

四.堆的源码呈现

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. // 定义堆结构
  5. typedef struct {
  6.     int* array;     // 存储堆元素的数组
  7.     int capacity;   // 堆的容量
  8.     int size;       // 堆中当前元素的个数
  9. } Heap;
  10.  
  11. // 创建堆
  12. Heap* createHeap(int capacity) {
  13.     Heap* heap = (Heap*)malloc(sizeof(Heap));
  14.     heap->array = (int*)malloc(sizeof(int) * capacity);
  15.     heap->capacity = capacity;
  16.     heap->size = 0;
  17.     return heap;
  18. }
  19.  
  20. // 交换两个元素
  21. void swap(int* a, int* b) {
  22.     int temp = *a;
  23.     *a = *b;
  24.     *b = temp;
  25. }
  26.  
  27. // 向堆中插入元素
  28. void insert(Heap* heap, int value) {
  29.     if (heap->size == heap->capacity) {
  30.         printf("堆已满，无法插入新元素。\n");
  31.         return;
  32.     }
  33.     
  34.     // 将新元素插入到堆的最后位置
  35.     heap->array[heap->size] = value;
  36.     
  37.     int currentIndex = heap->size;
  38.     int parentIndex = (currentIndex - 1) / 2;
  39.     
  40.     // 自下而上调整堆结构
  41.     while (currentIndex > 0 && heap->array[currentIndex] > heap->array[parentIndex]) {
  42.         swap(&heap->array[currentIndex], &heap->array[parentIndex]);
  43.         currentIndex = parentIndex;
  44.         parentIndex = (currentIndex - 1) / 2;
  45.     }
  46.     
  47.     heap->size++;
  48. }
  49.  
  50. // 从堆中删除并返回最大元素
  51. int deleteMax(Heap* heap) {
  52.     if (heap->size == 0) {
  53.         printf("堆为空，无法删除元素。\n");
  54.         return -1;
  55.     }
  56.     
  57.     int maxValue = heap->array[0];
  58.     
  59.     // 将最后一个元素移到堆顶
  60.     heap->array[0] = heap->array[heap->size - 1];
  61.     heap->size--;
  62.     
  63.     int currentIndex = 0;
  64.     int leftChildIndex = 2 * currentIndex + 1;
  65.     int rightChildIndex = 2 * currentIndex + 2;
  66.     
  67.     // 自上而下调整堆结构
  68.     while (1) {
  69.         int maxIndex = currentIndex;
  70.         
  71.         // 与左子节点比较
  72.         if (leftChildIndex < heap->size && heap->array[leftChildIndex] > heap->array[maxIndex]) {
  73.             maxIndex = leftChildIndex;
  74.         }
  75.         
  76.         // 与右子节点比较
  77.         if (rightChildIndex < heap->size && heap->array[rightChildIndex] > heap->array[maxIndex]) {
  78.             maxIndex = rightChildIndex;
  79.         }
  80.         
  81.         // 如果当前节点已经是最大值，则堆已调整完毕
  82.         if (maxIndex == currentIndex) {
  83.             break;
  84.         }
  85.         
  86.         // 否则，交换当前节点与最大子节点的位置
  87.         swap(&heap->array[currentIndex], &heap->array[maxIndex]);
  88.         currentIndex = maxIndex;
  89.         leftChildIndex = 2 * currentIndex + 1;
  90.         rightChildIndex = 2 * currentIndex + 2;
  91.     }
  92.     
  93.     return maxValue;
  94. }
  95.  
  96. // 打印堆元素
  97. void printHeap(Heap* heap) {
  98.     printf("堆元素：");
  99.     for (int i = 0; i < heap->size; i++) {
  100.         printf("%d ", heap->array[i]);
  101.     }
  102.     printf("\n");
  103. }
  104.  
  105. // 释放堆内存
  106. void destroyHeap(Heap* heap) {
  107.     free(heap->array);
  108.     free(heap);
  109. }
  110.  
  111. int main() {
  112.     Heap* heap = createHeap(10);
  113.     
  114.     insert(heap, 5);
  115.     insert(heap, 8);
  116.     insert(heap, 2);
  117.     insert(heap, 10);
  118.     insert(heap, 3);
  119.     
  120.     printHeap(heap);
  121.     
  122.     int max = deleteMax(heap);
  123.     printf("删除的最大元素：%d\n", max);
  124.     
  125.     printHeap(heap);
  126.     
  127.     destroyHeap(heap);
  128.     
  129.     return 0;
  130. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/573958
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号