golang 网站开发,做网站 什么语言好,公众号做电影采集网站会被封,微软做网站的软件堆排序是一种与插入排序和并归排序十分不同的算法。
优先级队列
Priority Queue
优先级队列是类似于常规队列或堆栈数据结构的抽象数据类型#xff08;ADT#xff09;。优先级队列中的每个元素都有一个相关联的优先级key。在优先级队列中#xff0c;高优先级的元素优先于…堆排序是一种与插入排序和并归排序十分不同的算法。
优先级队列
Priority Queue
优先级队列是类似于常规队列或堆栈数据结构的抽象数据类型ADT。优先级队列中的每个元素都有一个相关联的优先级key。在优先级队列中高优先级的元素优先于低优先级的元素。
虽然优先级队列通常使用堆heap实现但它们在概念上与堆不同。优先级队列是一种抽象的数据结构如列表或映射; 正如列表可以用链表或数组实现一样优先级队列也可以用堆或其他方法(如有序数组)实现。
堆
Heap
堆可以理解为由一个由数组来顺序存储的完全二叉树。
最大堆任意节点的key ≥ 子节点的key
类似的
最小堆任意节点的key ≤ 子节点的key
以最大堆为例来讲解
最大堆
最大堆的操作
build_max_heap根据一个未排序的数组生成一个最大堆
max_heapify: 如果子树的根节点违反最大堆的特性就对其进行纠正。max_heapify的前提是子树的左右子树都是最大堆。
build_max_heap的伪代码
for i n/2 down to 1do max_heapify(A,i)
max_heapify和build_max_heap的时间复杂度
对叶子结点上面一层的结点(level 1)进行max_heapify是O(1)的时间复杂度
对叶子结点上面i层 level i 的结点进行max_heapify是O(i)
n/4个结点是level 1n/8个结点是level 2n/16个结点是level 3 ... 1个结点是level logn
因此max_heapify的时间复杂度为O(logn)可计算出build_max_heap的时间复杂度为O(n)
计算过程在最底下
堆排序步骤
1.根据一个未排序的数组来创建最大堆
2.找到最大元素A[1]
3.交换元素A[n]和A[1]现在最大元素位于堆的尾部
4.移除A[n]最大元素只需将存放堆的数组的大小减1
5.经过交换元素之后的堆也许违背了最大堆的定义但是A[1]的孩子仍然是最大堆因此进行max_heapify经过修正后整个堆就是最大堆重复步骤2-5n次。
class Solution {
public://堆是一个完全二叉树因此适合使用顺序存储的方式。//堆排序步骤//1.根据一个未排序的数组来创建最大堆//2.找到最大元素A[1]//3.交换元素A[n]和A[1]现在最大元素位于堆的尾部//4.移除A[n]最大元素存放堆的数组的大小减1//5.经过交换元素之后的堆也许违背了最大堆的定义但是A[1]的孩子仍然是最大堆因此进行max_heapify经过修正后整个堆就是最大堆重复2-5n次//时间复杂度O(nlogn)vectorint sortArray(vectorint nums) {build_max_heap(nums);//堆排序int n nums.size();while(n 0){//重复n次//找到最大元素并与堆末尾元素进行交换int max_elem nums[0];nums[0] nums[n-1];nums[n-1] max_elem;--n;//移出末尾元素//进行max_heapifymax_heapify(nums, 0, n);}return nums;}void build_max_heap(vectorint nums){int size nums.size();for(int i size/2-1;i 0;--i){max_heapify(nums, i, size);}}void max_heapify(vectorint nums, int i, int size){//将A[i]修正为最大堆//A[i]的左孩子为A[2i1]右孩子为A[2i2]int left (i1) 1;int right left 1;int large left;//默认较大元素为左节点while(large size){if(right size nums[right] nums[left]){//假如右结点大于左节点large right;//记右结点为较大的}if(nums[i] nums[large]){//假如父节点小于左右结点中较大的结点//将父节点与较大的结点进行交换从而使父节点大于左右子结点符合最大堆的约束int tmp nums[i];nums[i] nums[large];nums[large] tmp;i large;//i调节为其子结点largelarge (i1) 1;//large调整为i的左子节点}else{break;}}}};
