赞
踩
堆的孩子和父亲的下标关系
已知父亲(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)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。