纯c实现堆 数据结构大全

c++小技巧

开���一个动态的二维数组

vector p(k,vector(n))

堆 

堆是一种非常有用的数据结构，主要有以下几个用途：

优先队列：堆是实现优先队列的一种有效方式。优先队列是一种特殊的队列，其中的元素按照它们的优先级进行排序。在最大堆中，最高优先级的元素总是位于堆顶；在最小堆中，最低优先级的元素总是位于堆顶。优先队列在很多算法中都有应用，例如 Dijkstra 的最短路径算法和 Prim 的最小生成树算法。

堆排序：堆可以用于实现一种有效的排序算法——堆排序。堆排序的时间复杂度是 O(n log n)，并且它是一种原地排序算法，不需要额外的存储空间。

查找最大/最小元素：在最大堆中，最大的元素总是位于堆顶，可以在 O(1) 的时间内找到；在最小堆中，最小的元素总是位于堆顶，也可以在 O(1) 的时间内找到。

Kth Element：堆可以用于高效地解决查找第 K 大（或第 K 小）元素的问题。这可以通过构建一个大小为 K 的最小堆（或最大堆）来实现，时间复杂度为 O(n log k)。

下面我们来是实现一下

头文件

先把一些函数跟头文件定义好

#pragma once#include#include#include#include#includetypedef int HPDataType;typedef struct Heap{HPDataType* a;int size;int capacity;}HP;void AdjustDown(HPDataType* a, int n, int parent);void AdjustUp(HPDataType* a, int child);void Swap(HPDataType* p1, HPDataType* p2);// 堆的构建void HeapCreate(HP* hp, HPDataType* a, int n);void HeapPrint(HP* php);void HeapInit(HP* php);void HeapDestroy(HP* php);// 保持他继续是一个堆 O(logN)void HeapPush(HP* php, HPDataType x);// 删除堆顶的数据，并且保持他继续是一个堆 O(logN)void HeapPop(HP* php);HPDataType HeapTop(HP* php);int HeapSize(HP* hp);// 堆的判空bool HeapEmpty(HP* hp);

打印

因为数组是底层逻辑，一个个打印即可

//打印void HeapPrint(HP* php){assert(php);for (int i = 0; i size; ++i){printf("%d ", php->a[i]);}printf("\n");}

初始化 

设置成NULL跟0其实都可以

// 初始化void HeapInit(HP* php){assert(php);php->a = NULL;php->size = php->capacity = 0;}

 销毁

// 销毁void HeapDestroy(HP* php){assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;}

交换 

为了方便，我们手搓一个交换，记得传地址，不要传值

// 交换void Swap(HPDataType* p1, HPDataType* p2){HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;}

向上调整 

先总结一下

堆的向上调整和向下调整通常在以下情况下进行：

1. 向上调整（Up-Heapify）：当我们向堆中插入一个新的元素时，新元素被放在堆的末尾，然后可能会破坏堆的性质（在最大堆中，父节点的值应该大于或等于其子节点的值；在最小堆中，父节点的值应该小于或等于其子节点的值）。为了恢复堆的性质，我们需要进行向上调整，即将新元素与其父节点进行比较，如果新元素违反了堆的性质，那么就交换新元素和其父节点的位置，然后继续向上调整，直到堆的性质被恢复。

2. 向下调整（Down-Heapify）：当我们从堆中删除最大元素（在最大堆中）或最小元素（在最小堆中）时，通常我们会移除堆顶的元素，然后将堆的最后一个元素移动到堆顶，这可能会破坏堆的性质。为了恢复堆的性质，我们需要进行向下调整，即将堆顶元素与其子节点进行比较，如果堆顶元素违反了堆的性质，那么就交换堆顶元素和其子节点的位置，然后继续向下调整，直到堆的性质被恢复。

总的来说，向上调整用于插入操作，向下调整用于删除操作。

// 向上调整void AdjustUp(HPDataType* a, int child){int parent = (child - 1) / 2;//while (parent >= 0)  不好while (child > 0){if (a[child] > a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}

向下调整 

// 向下调整void AdjustDown(HPDataType* a, int n, int parent){int child = parent * 2 + 1;while (child  
 推入元素
 
// 推入void HeapPush(HP* php, HPDataType x){assert(php);// 扩容if (php->size == php->capacity){int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);}
 
取出顶元素
 
// 弹出堆顶void HeapPop(HP* php){assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);}
 
其他 
 
 一些杂七杂八的功能，简单一点，但是官方有接口有我们也实现一下
 
// 看堆顶HPDataType HeapTop(HP* php){assert(php);assert(php->size > 0);return php->a[0];}// 堆的数量int HeapSize(HP* php){assert(php);return php->size;}// 堆的判空bool HeapEmpty(HP* php){assert(php);return php->size == 0;}
 
数组转化堆 
 
// 堆的构建void HeapCreate(HP* php, HPDataType* a, int n){assert(php);php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);if (php->a == NULL){perror("malloc fail");exit(-1);}memcpy(php->a, a, sizeof(HPDataType) * n);php->size = php->capacity = n;// 建堆算法for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(php->a, n, i);}}
 
例题
 
一个裸堆
  
#include #include #include using namespace std;priority_queue pq;long long add = 0;int main() {    int Q;    cin >> Q;    while (Q--)     {        int mid;        cin >> mid;        if (mid == 1)         {            long long x;            cin >> x;            pq.push(x - add);//最小堆        }         else if (mid == 2)         {            cout  x;            add += x;//每次输出加上        }    }    return 0;}