长春网站建设索q479185700,客户案例 网站设计,龙岩,企业所得税汇算清缴时间文章目录 1.堆的实现2.堆的应用--堆排序 大家在学堆的时候#xff0c;需要有二叉树的基础知识#xff0c;大家可以看我的二叉树文章#xff1a;二叉树
1.堆的实现 如果有⼀个关键码的集合 K {k0 , k1 , k2 , …#xff0c;kn−1 } #xff0c;把它的所有元素按完全⼆叉树… 文章目录 1.堆的实现2.堆的应用--堆排序 大家在学堆的时候需要有二叉树的基础知识大家可以看我的二叉树文章二叉树
1.堆的实现 如果有⼀个关键码的集合 K {k0 , k1 , k2 , …kn−1 } 把它的所有元素按完全⼆叉树的顺序存储⽅ 式存储在⼀个⼀维数组中并满⾜ Ki K2∗i1 Ki K2∗i1 且 Ki K2∗i2 i 0、1、2… 则称为⼩堆(或⼤堆)。将根结点最⼤的堆叫做最⼤堆或⼤根堆根结点最⼩的堆 叫做最⼩堆或⼩根堆。 如下就是堆的例子 堆有很多的应用例如①堆排序 ②TOP-K问题
堆的底层就是数组我们主要实现如下接口
//堆的初始化
void HeapInit(Heap* php);
// 堆的销毁
void HeapDestory(Heap* php);
// 堆的插入
void HeapPush(Heap* php, HPDataType x);
// 堆的删除
void HeapPop(Heap* php);
// 取堆顶的数据
HPDataType HeapTop(Heap* php);
// 堆的数据个数
int HeapSize(Heap* php);
// 堆的判空
int HeapEmpty(Heap* php);堆结构
typedef int HPDataType;typedef struct Heap
{HPDataType* _a;int _size;int _capacity;
}Heap;对于堆的初始化和销毁很简单
//堆的初始化
void HeapInit(Heap* php)
{assert(php);php-_a NULL;php-_size php-_capacity 0;
}// 堆的销毁
void HeapDestory(Heap* php)
{assert(php);php-_capacity php-_size 0;free(php-_a);php-_a NULL;
}对于堆的插入例如我们建一个小根堆我们每次插入一个数是把他放在堆尾的即数组的最后一个元素然后使用向上调整算法
Q什么是向上调整算法 A对于我们新插入来的数我们把他放在堆的最后一个元素上我们需要不断比较他即孩子节点与父节点谁小若父节点小则终止循环若孩子节点小则需要他和父节点交换位置并循环下去比代码如下
//向上调整算法建小堆
void AdjustUp(HPDataType* arr, int n)
{int child n - 1;while (child 0){int parent (child - 1) 1;if (arr[child] arr[parent]){swap(arr[child], arr[parent]);}child parent;}
}所以对于堆插入一个元素代码如下
// 堆的插入
void HeapPush(Heap* php, HPDataType x)
{assert(php);//判断是否需要增容if (php-_capacity php-_size){int newCapacity php-_capacity 0 ? 4 : 2 * php-_capacity;HPDataType* tmp (HPDataType*)realloc(php-_a, newCapacity * sizeof(HPDataType));if (tmp NULL){perror(realloc fail);exit(-1);}php-_capacity newCapacity;php-_a tmp;}php-_a[php-_size] x;//向上调整算法AdjustUp(php-_a, php-_size);
}对于堆的删除也就是我们要把最小的那个元素pop出来已知的是堆顶是最小的元素我们只需要让堆顶元素和最后一个元素互换然后size–然后在执行向下调整算法即可如下
//向下调整算法
void AdjustDown(HPDataType* arr, int n)
{int parent 0;int child parent * 2 1;while (child n){if (child 1 n arr[child 1] arr[child]) child child 1;if (arr[child] arr[parent]){swap(arr[child], arr[parent]);parent child;child parent * 2 1;}else break;}
}// 堆的删除
void HeapPop(Heap* php)
{assert(php);assert(!HeapEmpty(php));swap(php-_a[0], php-_a[php-_size - 1]);php-_size--;AdjustDown(php-_a, php-_size);
}余下的接口
// 取堆顶的数据
HPDataType HeapTop(Heap* php)
{assert(php);assert(!HeapEmpty(php));return php-_a[0];
}// 堆的数据个数
int HeapSize(Heap* php)
{assert(php);return php-_size;
}
// 堆的判空
int HeapEmpty(Heap* php)
{assert(php);return php-_size 0 ? 1 : 0;
}2.堆的应用–堆排序
我们想一想给我们传入一个数组让我们堆数组里面的元素进行排序需要注意的是向上调整算法和向下调整算法我们都要求除了他其他的都是一个堆。也就是我们需要对每个数据都进行一遍调整算法那么向上还是向下呢我们来分析一下时间复杂度 向上调整算法我们需要从第一个元素开始都进行一遍向上调算法 因此来说向上调整算法的时间复杂度是O(nlogn)为什么这么高我们可以想一下月考后面的元素在二叉树上呈现的是越多的而且他还要向上移动比较的次数更多那他的复杂度不就高了吗 向下调整算法这里我们不需要从最后一个元素开始向下调整我们只需要从最后一个非叶子节点开始向下调整算法即可 因此向下调整算法的时间复杂度为O(n)
注意这里是向下调整算法建堆的时间复杂度是O(n)但是单单一个元素向下调整算法是O(logn)的。
因此对于堆排序我们采用向下调整算法较优。
堆排序大家可以参考我的这篇文章堆排序
