189 8069 5689
堆的孩子和父亲的下标关系
已知父亲(parent)的下标
已知左孩子或右孩子下标(child)
下面这个数组逻辑上可以看作是一棵完全二叉树，通过从根节点开的向下调整算法可以把它调整成一个堆(大堆或小堆)，向下调整算法有以有一个前提：左右子树必须是一个堆，才能调整。我这里的是实现小堆的向下调整算法。
建小堆的向下调整的基本思路就是：从堆顶开始，拿自己和较小的一个孩子进行比较大小，如果小就进行交换然后把交换的位置当作父节点继续向下调整，如果两个孩子都比自己小就停止调整，否则一直调整到叶子节点。
// 向下调整(小堆)
void AdjustDown(HPDataType* arr, int n, int index)
{int parent = index;
int child = 2 * parent+1;
while (parent< n)
{ //找出两个孩子里的较小的
if (child< n && child + 1< n && arr[child] >arr[child + 1])
{ child++;
}
// 拿较小的孩子比较和父亲比价大小
if (child< n && arr[child]< arr[parent])
{ Swap(&arr[child], &arr[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{ //说明无需调整
break;
}
}
}堆的向下调整每次调整的一个节点，假设树的高度为 h h h最坏情况下调整的次数就是 h − 1 h-1 h−1，所以向下调整的时间复杂度就是树的深度 l o g 2 ( n − 1 ) log_{2}(n-1) log2(n−1)，最后得出 l o g 2 n log_{2}n log2n
堆的创建我们知道堆的向下调整算法必须满足左右子树都是一个堆，那有的时候是一个普通的数组，也就是一颗普通的完全二叉树，所以要通过建堆来让一个数组变成堆。
建堆的实现思路：从最后一个节点的父节点，也就是第一个非叶子节点的父亲开始不断向下调整，直到整课树都被调整成一个堆。
//向下调整建堆
int i = 0;
//从倒数第一个非叶子节点开始向下调整
for (i = (n - 2) / 2; i >= 0; --i)//n为数组元素个数
{AdjustDown(arr,n ,i);
}建堆的时间复杂度
我们知道时间复杂度就是计算最坏的时间复杂度，实际上就是计算一个满二叉树，这样每一棵树都会进行调整。
假设这一棵树的高度是 h h h
那么假设时间复杂度为 T n T_{n} Tn，时间复杂度就是从第一层到倒数第二层每个节点的调整次数之和
所以建堆的时间复杂度就是 O ( N ) O(N) O(N)，因为当 N N N足够大时，对数的大小就根本不值得一提了。
堆的向上调整算法堆的向上调整算法是用一个堆中，当我们要在堆的末尾插入一个新元素。
将堆顶元素和最后一个元素进行交换，然后将最后一个位置的元素进行向上调整。
如果是建小堆，拿最后一个元素和父节点进行比较，如果父节点大于自己就进行交换，接着以父节点的位置继续开始向上调整，如果不小于父节点就停止向上调整(说明此时已经满足小堆的条件了)。
// 交换函数
void Swap(HPDataType* x, HPDataType* y)
{HPDataType tmp = *x;
*x = *y;
*y = tmp;
}
// 向上调整(建小堆)
void AdjustUp(HPDataType* arr, int index)
{int child = index;
int parent = (child-1) / 2;//获取父节点下标
while (child >0)
{if (arr[parent] >arr[child])//如果节点如果大于孩子就交换
{ Swap(&arr[parent], &arr[child]);
child = parent;
parent = (child-1) / 2;
}
else
{ //说明无需调整
break;
}
}
}通过一维数组来实现一个逻辑上的完全二叉树，需要定义以下接口
堆的结构体
typedef int HPDataType;
typedef struct Heap
{HPDataType* arr;//数组
int size;//堆中元素个数
int capacity;//堆的容量
}Heap;// 交换函数
void Swap(HPDataType* x, HPDataType* y);
// 堆的创建
Heap* HeapCreate(HPDataType* arr, int n);
// 向下调整
void AdjustDown(HPDataType* arr, int n, int index);
// 向上调整
void AdjustUp(HPDataType* arr, int index);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType data);
// 堆的删除
void HeapPop(Heap* hp);
// 获取堆顶元素
HPDataType HeapTop(Heap* hp);
// 获取堆的元素个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);首先先通过malloc开辟空间
如果一个数组不是堆，在创建的时候就需要通过向下调整算法，从最后一个叶子节点的父亲开始调整，把它调整成一个小堆
// 交换函数
void Swap(HPDataType* x, HPDataType* y)
{HPDataType tmp = *x;
*x = *y;
*y = tmp;
}
// 堆的创建
Heap* HeapCreate(HPDataType* arr, int n)
{assert(arr);
Heap* heap = (Heap*)(malloc(sizeof(Heap)));
if (heap == NULL)
{printf("malloc erro!\n");
exit(-1);
}
heap->arr = (HPDataType*)(malloc(sizeof(HPDataType) * n));
heap->size = n;
heap->capacity = n;
memcpy(heap->arr, arr, sizeof(HPDataType) * n);
//向下调整建堆
int i = 0;
//从倒数第一个非叶子节点开始向下调整
for (i = (n - 2) / 2; i >= 0; --i)
{AdjustDown(heap->arr,heap->capacity ,i);
}
return heap;
}
// 向下调整
void AdjustDown(HPDataType* arr, int n, int index)
{int parent = index;
int child = 2 * parent + 1;
while (parent< n)
{ //找出两个孩子里的较小的
if (child< n && child + 1< n && arr[child] >arr[child + 1])
{ child++;
}
// 拿较小的孩子比较和父亲比价大小
if (child< n && arr[child]< arr[parent])
{ Swap(&arr[child], &arr[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{ //说明无需调整
break;
}
}
}// 堆的插入
void HeapPush(Heap* hp, HPDataType data)
{assert(hp);
//扩容
if (hp->size == hp->capacity)
{// 二倍扩容
HPDataType* ptr = (HPDataType*)(realloc(hp->arr, sizeof(HPDataType)*hp->capacity * 2));
if (ptr == NULL)
{ printf("扩容失败\n %s", strerror(errno));
exit(-1);
}
hp->arr = ptr;
hp->capacity = 2 * hp->capacity;
}
hp->arr[hp->size] = data;
//向上调整
AdjustUp(hp->arr,hp->size);
hp->size++;
}删堆顶元素实现思路
// 堆的删除
void HeapPop(Heap* hp)
{//堆中没有元素
assert(hp && hp->size != 0);
//拿堆顶元素和数组最后一个元素交换
Swap(&(hp->arr[0]), &(hp->arr[hp->size - 1]));
hp->size--;
//向下调整
AdjustDown(hp->arr, hp->size, 0);
}这个比价简单，就会返回数组 第一个元素就好
// 获取堆顶元素
HPDataType HeapTop(Heap* hp)
{assert(hp && hp->size != 0);
return hp->arr[0];
}
// 获取堆的元素个数
int HeapSize(Heap* hp)
{assert(hp);
return hp->size;
}// 堆的判空
int HeapEmpty(Heap* hp)
{assert(hp);
return hp->size == 0;
}// 堆的销毁
void HeapDestory(Heap* hp)
{assert(hp);
free(hp->arr);
hp->size = 0;
hp->capacity = 0;
hp->arr = NULL;
free(hp);
}Topk问题：给你一个组数据找出前k大的数
思路：对数组排序，取出前k个
size_t IntCmp(const void* x, const void* y)
{return *((int*)y) - *((int*)x);
}
void Test(int* arr, int n, int k)
{qsort(arr, n, sizeof(arr[0]), IntCmp);
int i = 0;
for (i = 0; i< k; i++)
{printf("%d ", arr[i]);
}
} qsort底层是通过快排实现的，而快排的时间复杂度为 n ∗ l o g 2 n n*log_{2}n n∗log2n
问题升级：能不能让时间复杂度在降低一点
此时就可以通过堆来解决这个问题
假设前面的找前k个大的数，建个小堆，因为小堆的堆顶一定是是一组数里最小的一个数字，如果来了一个数字比最小的数还要大，那么它肯定是要先如堆的。
于是写出代码
// 堆的创建
Heap* HeapCreate(HPDataType* arr, int n)
{assert(arr);
Heap* heap = (Heap*)(malloc(sizeof(Heap)));
if (heap == NULL)
{printf("malloc erro!\n");
exit(-1);
}
heap->arr = (HPDataType*)(malloc(sizeof(HPDataType) * n));
heap->size = n;
heap->capacity = n;
memcpy(heap->arr, arr, sizeof(HPDataType) * n);
//向下调整建堆
int i = 0;
//从倒数第一个非叶子节点开始向下调整
for (i = (n - 2) / 2; i >= 0; --i)
{AdjustDown(heap->arr,heap->capacity ,i);
}
return heap;
}
// 向下调整
void AdjustDown(HPDataType* arr, int n, int index)
{int parent = index;
int child = 2 * parent;
while (parent< n)
{ //找出两个孩子里的较小的
if (child< n && child + 1< n && arr[child] >arr[child + 1])
{ child++;
}
// 拿较小的孩子比较和父亲比价大小
if (child< n && arr[child]< arr[parent])
{ Swap(&arr[child], &arr[parent]);
parent = child;
child = 2 * parent;
}
else
{ //说明无需调整
break;
}
}
}
// 堆的删除
void HeapPop(Heap* hp)
{//堆中没有元素
assert(hp && hp->size != 0);
//拿堆顶元素和数组最后一个元素交换
Swap(&(hp->arr[0]), &(hp->arr[hp->size - 1]));
hp->size--;
//向下调整
AdjustDown(hp->arr, hp->size, 0);
}
// 获取堆顶元素
HPDataType HeapTop(Heap* hp)
{assert(hp && hp->size != 0);
return hp->arr[0];
}然后不断获取堆顶元素，不断删除堆顶元素，就能得到前K个小的数。于是 O ( n ) O(n) O(n)的时间复杂就解决了问题
问题继续升级：假设有100亿个整数，从中找出前10大的数。
此时用单纯用堆肯定行不通的，因为一个整形4个字节，那么100亿个整形就是400亿个字节，那么这就是将近40G的数据，如果单纯用堆肯定是不行的。
思路：建一个大小为10的小堆，不断往堆中插入元素，如果元素满了，就和堆顶比较，如果小就删除堆顶元素，然后再进行插入，直到遍历完整个数组。
那么此时的时间复杂度为 O ( n ) O(n) O(n)，而空间复杂度则是 O ( k ) O(k) O(k)
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧