二叉堆

堆的概念

• 如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元
  素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：
  Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为小堆(或大堆)。

• 小堆(大堆)中：任一结点的关键码均小于(大于)等于它的左右孩子的关键码，位于堆顶结点的关键码最小(最大)，从根节点到每个结点的路径上数组元素组成的序列都是递增(递减)的

• 堆存储在下标为0开始的数组中，因此在堆中给定下标为i的结点时：
  (1)如果i=0，结点i是根节点，没有双亲节点；否则结点i的双亲结点为结点(i-1)/2
  (2)如果2 i + 1 <= n - 1，则结点i的左孩子为结点2 i + 1，否则结点i无左孩子
  (3)如果2 i + 2 <= n - 1，则结点i的右孩子为结点2 i + 2，否则结
  点i无右孩子

堆的实现

将二叉树调整为最小堆的原理：
从最后一个非叶子结点开始调整，一直到根节点为止，将每个结点及其子树调整到满足小堆的性质即可

头文件的定义

#pragma once
#include <stdio.h>

#define MAX_SIZE 100

typedef struct Heap{
	int array[MAX_SIZE];
	int size;
}Heap;

堆的初始化

void HeapInit(Heap *pH,int arr[],int size)
{
	for (int i = 0; i < pH->size; i++)
	{
		pH->array[i] = arr[i];
	}
	pH->size = size;
}

堆的创建

//向下调整
void HeaoAdjustDown(Heap *pH,int root)
{
	int parent = root;

	while (1)
	{
		//当左孩子存在时
		int left = parent * 2 + 1;
		//判断左孩子是否越界
		if (left >= pH->size)
		{
			return;
		}

		//当一定有右孩子时
		int MaxChild = left;
		if (parent*2+2<pH->size && pH->array[parent*2+2]>MaxChild)
		{
			MaxChild = parent * 2 + 2;
		}

		if (pH->array[parent]>pH->array[MaxChild])
		{
			return;
		}

		int temp = pH->array[parent];
		pH->array[parent] = pH->array[MaxChild];
		pH->array[MaxChild] = temp;

		parent = MaxChild;
	}
}

//创建堆
void HeapMake(Heap *pH)
{
	for (int i = (pH->size-2)/2; i > 0; i--)
	{
		HeaoAdjustDown(pH,i);
	}
}

堆的插入操作

堆的插入：在已经建成的最小堆的后面插入新元素，插入之后，当树中结点不满足堆的性质时，就需要对堆进行重新调整

//插入
void HeapPush(Heap *pH,int data)
{
	assert(pH->size < MAX_SIZE);
	pH->array[pH->size++] = data;
	HeapAdjustUp(pH, pH->size - 1);
}

堆的插入操作

堆的删除：删除时每次删除堆顶元素
具体方法：将最后一个元素顶替堆顶元素，将堆中元素个数减少一个，相当于将堆中最后一个元素删掉，此时堆结构可能破坏，在向下调整使其满足堆的性质

//删除
void HeapPop(Heap *pH)
{
	pH->array[0] = pH->array[pH->size - 1];
	pH->size--;

	HeapAdjustUp(pH, 0);
}

堆排序

//升序
void HeapSort(int array[],int size)
{
	//建立大堆
	for ( int i = (size-2)/2; i > 0;  i--)
	{
		ArrayAdjustDown(array,size,i);
	}
	//开始排序
	for (int j = 0; j < size; j++)
	{
		int s = size - 1 - j;
		Swap(array, array + s);
		ArrayAdjustDown(array, size - 1 - j, 0);
	}
}

查找最小(大)的前K个数

100亿个数中找出最小的前K个数（海量数据top K问题）

int *TopK(int array[],int size,int k)
{
	int *heapArray = (int *)malloc(k * sizeof(int));
	assert(heapArray);
	
	//搬前K个数
	for (int i = 0; i < k; i++)
	{
		heapArray[i] = array[i];
	}
	//建立堆(大堆)
	for ( int j = (k-2)/2; j >= 0; j--)
	{
		ArrayAdjustDown(heapArray,k,j);
	}

	//将第K个与堆中最大元素比较
	for (int i = k; i < size; i++)
	{
		if (array[i] >= heapArray[0])
		{
			continue;
		}

		heapArray[0] = array[i];     //替换堆中最大元素
		ArrayAdjustDown(heapArray,k,0);
	}
	return heapArray;
}

测试部分

void TestHeap()
{
	int array[] = { 53, 17, 78, 9, 45, 65, 87, 23, 31 };
	int size = sizeof(array) / sizeof(int);

	Heap	heap;
	HeapInit(&heap, array, size);
	HeapMake(&heap);

	printf("建堆完成\n");
	
	//查找最小的前K个数
	int array[] = { 1,4,9,4,5,2,7,8,5,3,6,6,2,3 };
	int sz = sizeof(array) / sizeof(array[0]);

	int *ret = TopK(array, sz, 10);

	for (int i = 0; i < 10; i++)
	{
		printf("%d ",ret[i]);
	}

}