堆（数据结构）

目录

1.堆的定义：

1.堆是完全二叉树；

2.堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。

2.堆的代码实现： （小堆）

初始化（HeapInit）：

插入（HeapPush）：

删除堆顶元素（HeapPop）：

查看堆顶元素（HeapPeek）：

检查堆满（HeapFull）和堆空（HeapEmpty）：

销毁堆（HeapDestroy）：

堆化（Heapify）：

上滤（adjustup）和下滤（adjustdown）：

3.完整代码： 

---

1.堆的定义：

只要满足以下两个条件，就是堆（Heap）：

1.堆是完全二叉树；

若设二叉树的深度为h，除第 h 层外，其它各层 (1~h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

2.堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。

小堆：任何一个父亲<=孩子

大堆：任何一个父亲>=孩子

2.堆的代码实现： （小堆）

存储结构：

typedef int HeapDataType;
typedef struct Heap {
	HeapDataType* hp;
	int size;
	int capacity;
}Heap;

1. 初始化（HeapInit）：

   • 功能：为堆分配内存空间，并设置初始容量为n。
   • 细节：使用malloc为堆的数据元素分配内存，并设置堆的大小为0，容量为n。

   • void HeapInit(Heap*heap,int n) {
     	assert(heap);
     	HeapDataType* hp = (HeapDataType*)malloc(n * sizeof(HeapDataType));
     	if (hp == NULL) {
     		perror("HeapInit:malloc");
     		exit(1);
     	}
     	heap->hp = hp;
     	heap->capacity = n;
     	heap->size = 0;
     }
     

2. 插入（HeapPush）：

   • 功能：向堆中插入一个元素。
   • 细节：首先检查堆是否已满，如果已满则尝试扩大堆的容量。然后将新元素添加到堆的末尾，并通过adjustup函数调整堆的结构以保持小堆的性质（即父节点值不大于孩子节点值）。

   •  
     void HeapPush(Heap* heap,HeapDataType x) {
     	assert(heap);
     	if (HeapFull(heap)) {
     		int new = heap->capacity == 0 ? 4 : 2 * heap->capacity;
     		HeapDataType* tmp = (HeapDataType*)realloc(heap->hp, new * sizeof(HeapDataType));
     		if (tmp == NULL) {
     			perror("HeapPush:realloc");
     			exit(1);
     		}
     		heap->hp = tmp;
     		heap->capacity = new;
     	}
     	heap->hp[heap->size] = x;
     	adjustup(heap->hp, heap->size);
     	heap->size++;
     }
     

3. 删除堆顶元素（HeapPop）：

   • 功能：删除堆顶元素（即最小元素），并重新调整堆的结构。
   • 细节：首先检查堆是否为空。然后将堆的最后一个元素移到堆顶，并通过adjustdown函数重新调整堆以保持小堆性质。堆的大小减1。

   • void HeapPop(Heap* heap) {
     	assert(heap);
     	if (HeapEmpty(heap)) {
     		perror("HeapPop:NULL");
     		exit(1);
     	}
     	HeapDataType x = heap->hp[0];
     	heap->hp[0] = heap->hp[heap->size - 1];
     	heap->hp[heap->size - 1] = x;
     	heap->size--;
     	adjustdown(heap->hp, 0, heap->size);
     }
     

4. 查看堆顶元素（HeapPeek）：

   • 功能：返回堆顶元素的值，但不删除它。
   • 细节：直接返回堆顶元素的值。这通常用于查看当前最小元素的值，而不改变堆的结构。

   • HeapDataType HeapPeek(Heap*heap) {
     	assert(heap);
     	if (HeapEmpty(heap)) {
     		perror("HeapPeek:NULL");
     		exit(1);
     	}
     	return heap->hp[0];
     }
     

5. 检查堆满（HeapFull）和堆空（HeapEmpty）：

   • 功能：检查堆是否已满或是否为空。
   • 细节：HeapFull检查堆的大小是否等于其容量，而HeapEmpty检查堆的大小是否为0。

   • bool HeapFull(Heap*heap) {
     	return heap->capacity == heap->size;
     }
     

     bool HeapEmpty(Heap* heap) {
     	return heap->size == 0;
     }
     

6. 销毁堆（HeapDestroy）：

   • 功能：释放堆所占用的内存空间。
   • 细节：使用free函数释放堆的数据元素所占用的内存，并将堆的指针、容量和大小都重置为0。

   • void HeapDestory(Heap*heap) {
     	assert(heap&&heap->hp);
     	free(heap->hp);
     	heap->hp = NULL;
     	heap->capacity = 0;
     	heap->size = 0;
     }
     

7. 堆化（Heapify）：

   • 功能：将一个数组重新调整为小堆结构。
   • 细节：通常用于在堆构建完成后或在执行某些操作（如删除元素）后重新调整堆的结构。从最后一个非叶子节点开始，自底向上调整每个节点，以保持小堆的性质。

   • void Heapify(HeapDataType*a,int n) {
     	assert(a);
     	int i = (n - 1 - 1) / 2 ;
     	for (i; i >= 0; i--) {
     		adjustdown(a, i, n);
     	}
     }
     

8. 上滤（adjustup）和下滤（adjustdown）：

   • 功能：这两个函数用于在插入或删除元素后调整堆的结构。
   • 细节：adjustup用于在插入新元素后，从插入位置开始向上调整堆结构；adjustdown用于在删除堆顶元素后，从堆顶开始向下调整堆结构。这两个函数都通过比较节点与其子节点的值，并交换它们（如果需要）来保持小堆的性质。

   • void adjustup(HeapDataType*hp,int i) {
     	assert(hp);
     	int j = (i - 1) / 2;
     	while (j>=0) {
     		if (hp[i] < hp[j]) {
     			HeapDataType x = hp[i];
     			hp[i] = hp[j];
     			hp[j] = x;
     			i = j;
     			j = (i - 1) / 2;
     		}
     		else {
     			break;
     		}
     	}
     }
     

     void adjustdown(HeapDataType* hp, int i, int n) {
     	assert(hp&&i<n);
     	int j = 2 * i + 1;
     	if (hp[j] > hp[j + 1]&&j<n-1) {
     		j++;
     	}
     	if (hp[j] < hp[i]&&j<n) {
     		HeapDataType x = hp[i];
     		hp[i] = hp[j];
     		hp[j] = x;
     		adjustdown(hp, j, n);
     	}
     }
     

3.完整代码： 

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int HeapDataType;
typedef struct Heap {
	HeapDataType* hp;
	int size;
	int capacity;
}Heap;
//小堆
void adjustup(HeapDataType*hp,int i) {
	assert(hp);
	int j = (i - 1) / 2;
	while (j>=0) {
		if (hp[i] < hp[j]) {
			HeapDataType x = hp[i];
			hp[i] = hp[j];
			hp[j] = x;
			i = j;
			j = (i - 1) / 2;
		}
		else {
			break;
		}
	}
}
void adjustdown(HeapDataType* hp, int i, int n) {
	assert(hp&&i<n);
	int j = 2 * i + 1;
	if (hp[j] > hp[j + 1]&&j<n-1) {
		j++;
	}
	if (hp[j] < hp[i]&&j<n) {
		HeapDataType x = hp[i];
		hp[i] = hp[j];
		hp[j] = x;
		adjustdown(hp, j, n);
	}
}
void HeapInit(Heap*heap,int n) {
	assert(heap);
	HeapDataType* hp = (HeapDataType*)malloc(n * sizeof(HeapDataType));
	if (hp == NULL) {
		perror("HeapInit:malloc");
		exit(1);
	}
	heap->hp = hp;
	heap->capacity = n;
	heap->size = 0;
}
void Heapify(HeapDataType*a,int n) {
	assert(a);
	int i = (n - 1 - 1) / 2 ;
	for (i; i >= 0; i--) {
		adjustdown(a, i, n);
	}
}
void HeapDestory(Heap*heap) {
	assert(heap&&heap->hp);
	free(heap->hp);
	heap->hp = NULL;
	heap->capacity = 0;
	heap->size = 0;
}
bool HeapFull(Heap*heap) {
	return heap->capacity == heap->size;
}
bool HeapEmpty(Heap* heap) {
	return heap->size == 0;
}
void HeapPush(Heap* heap,HeapDataType x) {
	assert(heap);
	if (HeapFull(heap)) {
		int new = heap->capacity == 0 ? 4 : 2 * heap->capacity;
		HeapDataType* tmp = (HeapDataType*)realloc(heap->hp, new * sizeof(HeapDataType));
		if (tmp == NULL) {
			perror("HeapPush:realloc");
			exit(1);
		}
		heap->hp = tmp;
		heap->capacity = new;
	}
	heap->hp[heap->size] = x;
	adjustup(heap->hp, heap->size);
	heap->size++;
}
void HeapPop(Heap* heap) {
	assert(heap);
	if (HeapEmpty(heap)) {
		perror("HeapPop:NULL");
		exit(1);
	}
	HeapDataType x = heap->hp[0];
	heap->hp[0] = heap->hp[heap->size - 1];
	heap->hp[heap->size - 1] = x;
	heap->size--;
	adjustdown(heap->hp, 0, heap->size);
}
HeapDataType HeapPeek(Heap*heap) {
	assert(heap);
	if (HeapEmpty(heap)) {
		perror("HeapPeek:NULL");
		exit(1);
	}
	return heap->hp[0];
}
int main()
{
	Heap* heap = (Heap*)malloc(sizeof(Heap));
	HeapInit(heap, 5);
	HeapPush(heap, 4);
	HeapPush(heap, 2);
	HeapPush(heap, 15);
	HeapPush(heap, 7);
	HeapPush(heap, 9);
	for (int i = 0; i < 5; i++) {
		printf("%d ", heap->hp[i]);
	}
	HeapDestory(heap);
	return 0;
}