本文共 3004 字，大约阅读时间需要 10 分钟。

堆

堆，也叫做二叉堆。

目的：在堆中找到最值（最大值、最小值）       堆顶存放的不是最大值就是最小值 堆是已数组的形式存储的，但在逻辑上是完全二叉树 例如：

int arr[] = { 53, 17, 78, 9, 45, 65, 87, 23, 31 };

对应的堆为：

注：上述堆还未进行调整

typedef int DataType;	//堆的结构体	typedef struct Heap	{		DataType arr[MAX_SIZE];		int size;	}Heap;

向下调整

如果一个结点的下标为root，则

    左孩子：root * 2 + 1

    右孩子：root * 2 + 2

    父结点：(root - 1) / 2

void Swap(int *pa, int *pb)	{		int tmp = *pa;		*pa = *pb;		*pb = tmp;	}	//size表示数组元素个数，root要调整元素的下标	void AdjustDown(DataType arr[], int size, int root)	{		while (1)		{			int left = root * 2 + 1;			int right = root * 2 + 2;			if (left >= size)			{				return;			}			int max = left;			if (right < size && arr[right] > arr[max])			{				max = right;			}			if (arr[max] < arr[root])			{				return;			}			Swap(arr + max, arr + root);			root = max;		}	}

堆的创建

大堆

void CreateHeap(DataType arr[], int size)	{		//因为要找到最后一个叶子结点的父结点进行调整，所以i从(size - 2) / 2开始		for (int i = (size - 2) / 2; i >= 0; i--)		{			AdjustDown(arr, size, i);		}	}

小堆

void AdjustDownSmall(DataType arr[], int size, int root)	{		while (root * 2 + 1 < size)		{			int min;			if ((root * 2 + 2 < size) && (arr[root * 2 + 2] < arr[root * 2 + 1]))			{				min = root * 2 + 2;			}			else			{				min = root * 2 + 1;			}			if (arr[root] < arr[min])			{				return;			}			Swap(&arr[root], &arr[min]);			root = min;		}	}	//	void CreateHeapSmall(DataType arr[], int size)	{		//因为要找到最后一个叶子结点的父结点进行调整，所以i从(size - 2) / 2开始		for (int i = (size - 2) / 2; i >= 0; i--)		{			AdjustDownSmall(arr, size, i);		}	}

堆的初始化

//ph->arr表示调整后的数组，arr表示原来的数组，size表示数组元素的个数	void HeapInit(Heap *ph, DataType arr[], int size)	{		assert(size <= MAX_SIZE);		memcpy(ph->arr, arr, sizeof(DataType) * size);		ph->size = size;			CreateHeapSmall(ph->arr, ph->size);	}

堆顶元素

DataType HeapTop(Heap *ph)	{		assert(ph->size > 0);		return ph->arr[0];	}

堆的插入

规则：在最后一个叶子结点后面在插入一个结点，然后进行调整

void HeapPush(Heap *ph, DataType data)	{		assert(ph->size < 100);		ph->arr[ph->size] = data;		ph->size++;		AdjustDown(ph->arr, ph->size, (ph->size - 2) / 2);	}

堆的删除

规则：删除堆顶元素，将最后一个叶子结点放在堆顶，进行调整

void HeapPop(Heap *ph)	{		assert(ph->size > 0);		ph->arr[0] = ph->arr[ph->size - 1];		ph->size--;		AdjustDown(ph->arr, ph->size, 0);	}

向上调整

void AdjustUpBig(DataType arr[], int size, int child)	{		while (child > 0)		{			int parent = (child - 1) / 2;			if (arr[child] < arr[parent])			{				return;			}			Swap(arr + child, arr + parent);			child = parent;		}	}

注：向上调整是知道孩子结点，查询父结点开始调整

    向下调整是知道父节点，查询孩子结点开始调整

TopK

查询一组数据中，前K个最大的元素

第一步：取前K个元素出来，创建一个只有K个元素的小堆 第二步：将堆顶元素与剩下的元素一一比较，         堆顶元素大：return         堆顶元素小：将堆顶元素更换，进行调整

void HeapTopK(DataType arr[], int size, int k)	{		int *heap = (int *)malloc(k * sizeof(int));		for (int i = 0; i < k; i++)		{			heap[i] = arr[i];		}		CreateHeapSmall(heap, k);		for (int i = k; i < size; i++)		{			if (arr[i] < heap[0])			{				continue;			}			heap[0] = arr[i];			AdjustDownSmall(heap, k, 0);		}			for (int i = 0; i < k; i++)		{			printf("%d ", heap[i]);		}		free(heap);	}

注：上述所有的root都表示下标，在堆中只是用到了二叉树的思想，但真正的还是操作数组，一定不能出现root->left的情况