算法 之 堆 - 小结

之前我们讨论的堆，都把最大键值存储在根节点中，这种类型的堆可以看作是最大堆。

我们还可以创建另一种堆，把最键小值存储在根节点中，根节点以外的节点的键值，大于或等于存储在它父节点中的键值，这种类型的堆可以看作是最小堆。

具体是用最大堆还是最小堆，就根据我们自身的需要来选择了。

 

堆的算法到这里就讲完了，下面这段代码包括了之前讲过的堆的所有算法：

#include <stdio.h>
#include <stdlib.h>

void siftUp(int* heap, int index);
void siftDown(int* heap, int index);
void siftDown(int* heap, int siftDownTo, int index);
int* insertElement(int* heap, int element);
int* deleteElement(int* heap, int index);
int* makeHeap(int* array, int arrayLength);
void heapSort(int* heap);
void print(char* description, int* heap);

void siftUp(int* heap, int index)
{
	int heapLength = heap[0];

	if (index < 1 || index > heapLength)
		return;

	bool done = false;
	while(!done && index > 1)
	{
		if (heap[index] > heap[index / 2])
		{
			int temp = heap[index];
			heap[index] = heap[index / 2];
			heap[index / 2] = temp;
		}
		else
		{
			done = true;
		}

		index /= 2;
	}
}

void siftDown(int* heap, int index)
{
	int heapLength = heap[0];
	siftDown(heap, heapLength, index);
}

void siftDown(int* heap, int siftDownTo, int index)
{
	if (index < 1 || index * 2 > siftDownTo)
		return;

	bool done = false;
	while(!done && index * 2 <= siftDownTo)
	{
		index *= 2;

		if (index + 1 <= siftDownTo && heap[index + 1] > heap[index])
			index += 1;

		if (heap[index] > heap[index / 2])
		{
			int temp = heap[index];
			heap[index] = heap[index / 2];
			heap[index / 2] = temp;
		}
		else
		{
			done = true;
		}
	}
}

int* insertElement(int* heap, int element)
{
	int heapLength = heap[0];
	int resultHeapLength = heapLength + 1;

	// 创建一个长度为resultHeapLength+1的int数组
	int* resultHeap = (int*)malloc(sizeof(heap) * (resultHeapLength + 1));
	if (resultHeap == NULL)
		return NULL;

	resultHeap[0] = resultHeapLength;
	for (int i = 1; i <= heapLength; i++)
	{
		resultHeap[i] = heap[i];
	}

	resultHeap[resultHeapLength] = element;
	siftUp(resultHeap, resultHeapLength);

	return resultHeap;	
}

int* deleteElement(int* heap, int index)
{
	int heapLength = heap[0];
	if (index < 1 || index > heapLength)
		return heap;

	int x = heap[index];
	int y = heap[heapLength];

	int resultHeapLength = heapLength - 1;

	// 创建一个长度为resultHeapLength+1的int数组
	int* resultHeap = (int*)malloc(sizeof(heap) * (resultHeapLength + 1));
	if (resultHeap == NULL)
		return NULL;

	resultHeap[0] = resultHeapLength;
	for (int i = 1; i <= resultHeapLength; i++)
	{
		resultHeap[i] = heap[i];
	}

	if (index == resultHeapLength)
		return resultHeap;

	resultHeap[index] = y;
	if (y > x)
	{
		siftUp(resultHeap, index);
	}
	else
	{
		siftDown(resultHeap, index);
	}

	return resultHeap;
}

int* makeHeap(int* array, int arrayLength)
{
	if (array == NULL || arrayLength <= 0)
		return NULL;

	int heapLength = arrayLength;
	int* heap = (int*)malloc(sizeof(array) * (heapLength + 1));
	if (heap == NULL)
		return NULL;

	// heap[0]用来存储数组中堆数据的长度，堆数据heap[1]...heap[heapLength]  
	// 所以数组的实际长度是heapLength+1，我们只对从数组索引为1开始的heapLength个数据进行操作
	heap[0] = heapLength;
	for (int i = 0; i < arrayLength; i++)
	{
		heap[i + 1] = array[i];
	}

	for (int i = heapLength / 2; i >= 1; i--)
	{
		siftDown(heap, i);
	}

	return heap;
}

void heapSort(int* heap)
{
	if (heap == NULL)
		return;

	int heapLength = heap[0];
	int temp = 0;

	for (int i = heapLength; i >= 2; i--)
	{
		temp = heap[1];
		heap[1] = heap[i];
		heap[i] = temp;

		siftDown(heap, i - 1, 1);
	}
}

void print(char* description, int* heap)
{
	printf("%s:\t", description);

	int heapLength = heap[0];

	for(int i = 1; i <= heapLength; i++)
	{
		printf("%d ", heap[i]);
	}

	printf("\n");
}

void main()
{
	const int ARRAY_LENGTH = 10;
	int array[ARRAY_LENGTH] = { 4, 3, 8, 10, 11, 13, 7, 30, 17, 26 };

	int* heap = makeHeap(array, ARRAY_LENGTH);
	print("从数组初始化堆", heap);

	int* heapAfterInsert = insertElement(heap, 20);
	print("插入新数据20", heapAfterInsert);
	free(heap);

	int* heapAfterDelete = deleteElement(heapAfterInsert, 2);
	print("删除第2个数据", heapAfterDelete);
	free(heapAfterInsert);

	heapSort(heapAfterDelete);
	print("按非降序排序", heapAfterDelete);
	free(heapAfterDelete);

	getchar();
}

 

更多内容请参考：

算法 之 堆 - 简介

算法 之 堆 - Sift-up和Sift-down

算法 之 堆 - 插入和删除

算法 之 堆 - 创建堆

算法 之 堆 - 排序