堆的概念
-
如果有一个关键码的集合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]);
}
}