-
数据结构堆的时间复杂度(最大堆,最小堆)
2021-03-11 19:38:24创建堆的方式有两种,一种是一边插入结点,一边调用堆的插入方法调整堆,这样的时间复杂度就是 O(NlogN),而第二种方式就把时间复杂度缩减到了O(N),它是采用先把结点插入好了,然后再来调整堆,并不是一边插入一边...创建堆的方式有两种,一种是一边插入结点,一边调用堆的插入方法调整堆,这样的时间复杂度就是
O(NlogN),而第二种方式就把时间复杂度缩减到了O(N),它是采用先把结点插入好了,然后再来调整堆,并不是一边插入一边调整。
但是从代码层面来看,可能会误以为第二种方式的时间复杂度也是O(NlogN),但第二种方式是从下往上建立堆。举个例子,如下所示,假设堆中存在了N个节点(满足堆的性质),采用第一种方式,再创建N个结点,那么插入第一个数时,就调用了时间复杂度为logN的插入方法,插入N个数后,时间复杂度为logN。
让我们看看第二种方式会如何?
先把N个结点创建到树中,把这N个结点具体化,我们看到在调整树时,第一次是以倒数第二层的结点作为根节点,然后来调整这棵子树,也就是它的时间复杂度不再是logN了,因为远远没到N个结点,远远没到整颗树的高度,它的时间复杂度应该如下判断,在最坏情况下,树中每个结点,会一直向下查找,一直到底,假设树高为h,则倒数第二层会向下查找1次,倒数第三层会向下查找2次…
倒数第二层结点数为2(h-2),倒数第三层2h-3…
JAVA代码实现
import java.util.ArrayList; import java.util.Arrays; //必须传入一个Comparable的实现类,因为后续会用到类的内部比较器 public class Heap<E extends Comparable> { Comparable<? super E>[] list;//堆--存储Comparable的实现类 int size; //堆长度 int capacity;//堆容量 public Heap(int capacity){ this.capacity=capacity; size=0; list=new Comparable[capacity+1]; } //初始化 public void Init(E value,int index){ if(index>0) { list[index]= value; size++; } else new RuntimeException("下标越界"); } //创建堆 public void Build_Max_Heap(){ for(int i=size/2;i>0;i--){ int child=0; int parent = i; Comparable par_X= (E) list[i]; for(;parent*2 <= size;parent=child){ child=parent*2; if(child+1<=size && list[child].compareTo((E) list[child+1]) ==-1) child++; if(par_X.compareTo((E) list[child])==1) break; list[parent]=list[child]; } list[parent]=(E) par_X; } } //插入堆 public void Insert(E node){ list[++size]=node; for(int i=size;i/2>=0;i=i/2){ if(i==1 || list[i/2].compareTo((E)node)==1){ list[i]=node; break; } else{ list[i]=list[i/2]; } } } //删除堆 public E Delete(){ Comparable DeleteX=list[1]; Comparable X=list[size--]; int child=1; int parent=1; for(;parent*2<=size;parent=child){ child=parent*2; if(child+1<=size && list[child].compareTo((E)list[child+1])==-1 ) child++; if(X.compareTo((E)list[child])==-1) list[parent]=list[child]; else break; } list[parent]=X; return (E)DeleteX; } //测试数据 public static void main(String[] args) { Heap<SSS> heap = new Heap<>(10); heap.Init(new SSS(1),1); heap.Init(new SSS(2),2); heap.Init(new SSS(3),3); heap.Init(new SSS(4),4); heap.Init(new SSS(5),5); heap.Insert(new SSS(6)); heap.Build_Max_Heap(); heap.Delete(); for(int i=1;i<=heap.size;i++) System.out.println(heap.list[i]); } } class SSS implements Comparable { int X; @Override public int compareTo(Object o) { SSS s2=(SSS) o; if(X>s2.X) return 1; if(X<s2.X) return -1; else return 0; } public SSS(int X){ this.X=X; } @Override public String toString() { return "SSS{" + "X=" + X + '}'; } }
-
堆排序时间复杂度_py排序-堆排序heapSort
2020-11-27 02:23:57堆排序思想:堆排序,利用堆这种数据结构设计的一种排序...将堆顶元素与末尾元素进行交换,使末尾元素最大/最小,则末尾就是排好序的数组。然后继续调整堆为大顶堆/小顶堆。再将堆顶元素与末尾元素交换,得到第二大...堆排序思想:
- 堆排序,利用堆这种数据结构设计的一种排序算法,是选择排序的一种。
- 堆是一种近似完全二叉树的数据结构,并且:子节点的键值或索引总是小于(或者大于)它的父节点。
算法描述:
- 构造初始堆。将给定无序序列构造成一个堆(一般升序采用大顶堆,降序采用小顶堆);
- 将堆顶元素与末尾元素进行交换,使末尾元素最大/最小,则末尾就是排好序的数组。
- 然后继续调整堆为大顶堆/小顶堆。
- 再将堆顶元素与末尾元素交换,得到第二大元素;
- 重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素;
- 如此反复进行交换、重建、交换,直到整个序列有序。
参考:
- https://zhuanlan.zhihu.com/p/73714165
- https://zhuanlan.zhihu.com/p/142673431
- 南风以南:python实现·十大排序算法之堆排序(Heap Sort)
我的理解之大白话:
好不容易看懂了,咱必须得唠唠,(害,写的啥玩意,感觉语句不通的):
- 首先,堆,大顶堆,小顶堆的定义都很明显。下图里左右分别为大顶堆和小顶堆。
https://blog.csdn.net/qq_28063811/article/details/93034625 2. 我在思考的时候,就觉得有三个问题骚扰着我:
- 列表和树怎么建立关系?
- emmm很简单,例如上面那个大顶堆,写成数组就是[9,5,8,2,3,4,7,1]
- 哈哈哈其实就是树的按行读取啦。
- 所以不要怀疑,[9,5,8,2,3,4,7,1]就是上面那棵树,上面那棵树就是[9,5,8,2,3,4,7,1]
- 对于待排序序列:[91, 60, 96, 13, 35, 65, 46, 65, 10, 30, 20, 31, 77, 81,22],我们先给他画成树的形式。如下图,而我们的目标是把他转化为大顶堆。
- 我怎么把给序列的一般树排序成大顶堆呢?
- 这就是堆排序算法里的重点了,我们将问题拆解,根据堆关于父子节点数值问题的定义,其实这个树可以拆解为众多的 父节点和子节点 组,比如上图,基本单位就是[91,60,96] [60,13,35] [96,65,46], [13,65,10], [35,30,20], [65,31,77], [46,81,22]。我们只要保证这些基本单位都满足堆的定义,那么就肯定没得问题了。
- 那么问题来了,怎么确保单元内部满足堆的条件呢?
- 首先需要解决的就是,数组id和数据在树中的位置关系。在数组里,父节点和字节点怎么确定,那么通过找规律我们可以发现,父节点index是 n 的话,那么其左右节点就是 2n+1 , 2n+2。
- 那么基本单位的排序顺序怎么订?我们是从上而下调整基本单位?还是从下而上呢?答案是从下而上。有人回答啦,我觉得还挺在理:“堆是一个二叉树,以最大堆为例,建堆的本质是让这颗二叉树满足父节点的值大于等于子节点节点。自底向上本质上就是一个倒序的层次遍历,每个层上的元素与自己的孩子比较一下,保证自己大于子节点,最后堆顶一定是最大值。通过层层向上的方式,符合堆性质的区域从底层向上扩张,最终建堆完成。如果是自顶向下,当第i层和他的孩子i+1层比较中出现交换,交换后的i层不能保证小于i-1层,于是又要向上验证,最坏情况是验证到顶。”
链接在这:https://www.zhihu.com/question/65501536 - 然后既然是基本单元,就知道肯定存在迭代的啦。出现交换的话肯定要迭代进行判断交换后的是否依旧满足。这个代码中会体现。
- 排成这个样子之后我怎么取出来?
- 问题来了,我排成大顶堆,只能说最顶层的数值最大,其他还是不确定,也不能得到排序后的结果。
- 这就对了,我们排好大顶堆之后啊,其实只能拿到一个最大的值,咱们就默默的把他和数组最后一位 的数据进行交换,那么咱们的最后一位数字是不是就相当于排序好了呀。然后刚才本来的最后一位被放在根节点了,这又不是大顶堆了,我们就需要对这个交换后的树重新堆排序,再排个第二大的数据出来,当然这个去排序的树,肯定要砍掉刚才被放到最后一位的最大数了。
- 然后就是 拿出一位最大数,再堆排序,再拿,直到全部排完,我们就结束啦。
写了半天,咱也不知道自己写了个啥玩意。上代码吧还是您。
python代码实现:
def buildHeap(sortList,lenS,target): # 堆树的基本单元进行整理 largest = target left,right = 2*target+1, 2*target+2 # 如果是逆序排序,直接把下面两个if里面的大于号换成小于号,构建小顶堆就行了 if left<lenS and sortList[left]>sortList[target]: largest = left if right<lenS and sortList[right]>sortList[largest]: largest = right if largest != target: sortList[largest],sortList[target] = sortList[target],sortList[largest] # 发生交换,则进行迭代整理 buildHeap(sortList,lenS,largest) def heapSort(sortList): lenS = len(sortList) # 最后一个父节点的id last_root = lenS//2-1 # 自底向上构建堆 for i in range(last_root,-1,-1): buildHeap(sortList, lenS, i) # 取出堆顶元素,进行排序 for end in range(lenS-1, 0, -1): sortList[0], sortList[end] = sortList[end], sortList[0] # end每次都会减1,所以就自动排除后面已经排序好的数据了 buildHeap(sortList, end, 0) return sortList print(heapSort([1,9,8,6,9,2,9,5,4,3,8]))
- 时间复杂度:
【好坏都是
】
- 空间复杂度:
【一直都在原址修改】
- 不稳定排序
ps:排序算法稳定性的判定
- 稳定:如果
原本在
前面,而
,排序之后
仍然在
的前面。
- 不稳定:如果
原本在
的前面,而
,排序之后
可能会出现在
的后面。
至于时间复杂度怎么算的:放过我吧老天爷啊啊啊啊啊
-
堆排序 两种实现(最小堆和最大堆)
2018-07-06 14:27:23堆排序算法是建立在二叉树的堆结构上的,通过交换堆(一维数组)中的元素,并进行上浮或下沉函数运算实现多次调整 堆排序算法的复杂度低,和快速排序属于相同速度级别的一种快速的排序算法 下面以最小堆原文地址为:堆排序 两种实现(最小堆和最大堆)
堆排序算法是建立在二叉树的堆结构上的,通过交换堆(一维数组)中的元素,并进行上浮或下沉函数运算实现多次调整
堆排序算法的复杂度低,和快速排序属于相同速度级别的一种快速的排序算法
下面以最小堆和最大堆来进行堆排序算法的实现,具体内容在代码中进行讲解
1.最小堆 堆排序
#include"iostream"
#include"cstdio"
using namespace std;
int h[100]; //堆
int n;
int num; //num的意义在于,在n的值不断减小的时候,保存n原来的值,以便我们在最后输出排序后的数组的时候,丢失原来的数组元素个数的值
void swap(int x,int y) //必要的交换函数
{
int t;
t=h[x];
h[x]=h[y];
h[y]=t;
}
void siftdown(int i) //子树的向下调整,构建局部最小堆
{
int t,flag=0;
while(i*2<=n&&flag==0)
{
if(h[i]>h[i*2])
{
t=2*i;
}
else
{
t=i;
}
if(i*2+1<=n)
{
if(h[t]>h[2*i+1])
{
t=2*i+1;
}
}
if(t!=i)
{
swap(t,i);
i=t;
}
else
{
flag=1;
}
}
}
/*void siftup(int i)
{
int flag=0;
if(i==1)
{
return ;
}
else
{
while(i!=1&&flag==0)
{
if(h[i]<h[i/2])
{
swap(i,i/2);
i=i/2;
}
else
{
flag=1;
}
}
}
}*/
int delet() //每次返回对顶元素,堆顶元素出堆的顺序是排序好的
{
int t;
t=h[1];
h[1]=h[n]; //交换的目的是和下面的n--和siftdown共同保证每次出堆的是标准的要求的顺序
n--;
siftdown(1);
return t;
}
int main()
{
cin>>n;
num=n;
for(int i=1;i<=n;i++)
{
scanf("%d",&h[i]);
}
for(int i=n/2;i>=1;i--)
{
siftdown(i);
}
for(int i=1;i<=num;i++)
{
printf("%d ",delet());
}
return 0;
}2.最大堆 堆排序
#include"iostream"
#include"cstdio"
using namespace std;
int h[100];
int n;
int num;
void swap(int x,int y)
{
int t;
t=h[x];
h[x]=h[y];
h[y]=t;
}
void siftdown(int i) //构建最大数的siftdown下沉函数
{
int t,flag=0;
while(i*2<=n&&flag==0)
{
if(h[i]<h[i*2])
{
t=2*i;
}
else
{
t=i;
}
if(i*2+1<=n)
{
if(h[t]<h[i*2+1])
{
t=2*i+1;
}
}
if(t!=i)
{
swap(t,i);
i=t;
}
else
{
flag=1;
}
}
}
void heapsort() //heapsort堆排序函数
{
while(n>1)
{
swap(1,n);
n--; //这三句的目的是将最大的元素不断从堆顶有序的排列到堆尾,以便最后进行整体输出
siftdown(1);
}
}
int main()
{
cin>>n;
num=n;
for(int i=1;i<=n;i++)
{
scanf("%d",&h[i]);
}
for(int i=n/2;i>=1;i--)
{
siftdown(i);
}
heapsort();
for(int i=1;i<=num;i++)
{
printf("%d ",h[i]);
}
return 0;
}
转载请注明本文地址:堆排序 两种实现(最小堆和最大堆) -
树_最小堆
2015-10-05 13:46:15以下是最小堆添加节点和删除最小节点的功能实现。 特点: A.完全二叉树(降低高度)。 B.充分利用数组存储,通过下标可以直接找到父子关系。 C.插入新元素和/删除最小元素不需要大量移动,最坏只需要进行logN...以下是最小堆添加节点和删除最小节点的功能实现。
特点:
A.完全二叉树(降低高度)。
B.充分利用数组存储,通过下标可以直接找到父子关系。
C.插入新元素和/删除最小元素不需要大量移动,最坏只需要进行logN次重新调整即可。
D.获取最小值时间复杂度O(1)。
E.操作过程适合实现优先队列。
F.堆排序时间复杂度O(NlogN)。class Heap { public: typedef int key_t; Heap(size_t max = 64); ~Heap(); key_t GetMin(); bool Add(key_t key); bool RemoveMin(); private: size_t _max; size_t _count; key_t *_nodes; }; Heap::Heap(size_t max) : _max(max),_count(0),_nodes(NULL) { if (_max) _nodes = new key_t[_max+1]; } Heap::~Heap() { if (_nodes) delete []_nodes; } Heap::key_t Heap::GetMin() { return _count > 0 ? _nodes[1] : numeric_limits<int>::min(); } bool Heap::Add(key_t key) { int curIndex; if (_count < _max) { _nodes[++_count] = key; curIndex = _count; while(curIndex > 1) { if(_nodes[curIndex] < _nodes[curIndex/2]) { key_t tmp = _nodes[curIndex/2]; _nodes[curIndex/2] = _nodes[curIndex]; _nodes[curIndex] = tmp; curIndex /= 2; } else { return true; } } } else { cout<<"===>Can't be inserted, limit to maxmium!"<<endl; return false; } return true; } bool Heap::RemoveMin() { if (_count) { size_t curIndex = 1, min; _nodes[1] = _nodes[_count--]; while(2*curIndex <= _count) { min = 2*curIndex; if (2*curIndex+1 <= _count) { min = _nodes[2*curIndex] < _nodes[2*curIndex+1] ? 2*curIndex : 2*curIndex+1; } if (_nodes[curIndex] > _nodes[min]) { key_t tmp = _nodes[curIndex]; _nodes[curIndex] = _nodes[min]; _nodes[min] = tmp; curIndex = min; } else { return true; } } return true; } cout<<"===>Can't be removed, heap is already empty!"<<endl; return false; }
-
最小堆 :完全二叉树,能方便地从中取出最小/大元素
2017-05-26 15:52:30* 堆的插入(插入到堆尾,再自下向上调整为最小堆) * 堆的删除(删除堆顶元素并用堆尾元素添补,再自上向下调整为最小堆) * 堆排序(时间复杂度:O(nlgn),空间复杂度O(1),不稳定):升序排序一般用最大 -
优先队列(堆)的构建时间复杂度分析
2014-02-20 12:23:11本文以最小堆为例,构建堆的过程是首先初始化一个数组a,其中a[0]存数组的长度n,即第一个有效元素从a[1]开始,这样保证左孩子为2*i,右孩子为2*I+1;然后从(n - 1)/2开始,每次向下调整一个元素,直到n = 0。 ... -
包含min函数的栈-最小堆的插入、删除(调整)
2020-04-28 11:52:17定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。 注意:保证测试中不会当栈为空的时候,对栈调用pop()或者min()或者top()方法。 解答: class Solut... -
c语言最小堆的实现-优先队列
2017-02-25 15:07:48libevent 中有定时事件的管理,用户可以把超时的定时事件插入到 管理器...查看了源码发现,定时器的数据结构其实是由最小堆来实现的。 优先队列为完全二叉树,所以在插入调整的时间复杂度为 O(N),弹出的复杂度为O(1); -
算导--6.5-9使用最小堆完成k路归并问题
2016-03-12 22:32:39思路:建一个大小为k的堆,堆中的每个元素代表一个List,元素的key为List当前最小元素的值,调整为最小堆,取出堆顶的元素,并记录到排序结果中,然后插入相应List中下一个元素的值作为新的堆顶元素key的值,然后... -
【数据结构】【c】【堆】堆排序算法详解(复杂度、前提、自顶向下算法、应用场景)
2019-08-18 09:45:49堆作为一种特殊的数据结构,它的排序也非常有意思。和冒泡排序、选择排序一样,他们都能求出顺序表的第n大的数据。...交换堆顶的元素和最后一个元素,此时最后一个位置作为有序区,然后进行其他无序区的堆调整,重... -
二.用最小堆方法找出海量数据中最小的k个数
2015-06-26 12:21:20思路:用数组b模拟海量数据的数组,数组a存放最小的k个数,首先将数组b的前k个数赋值给a,对a建最大堆,则此时a[0]存放a的最大元素,然后遍历b中...调整堆用时logk,遍历b用时n,时间复杂度nlogb #include using names -
堆
2021-02-24 09:38:50- 最小堆 #二叉堆的操作: - 插入节点 插入节点在完全二叉树的最后一个位置,不断“上浮”节点调整堆,复杂度为O(logn) - 删除节点 删除堆顶节点,把最后一个节点值补到堆顶,然后不断“下沉”操作,复杂度为O(logn... -
从n个元素中选取第k大的元素,设计一个算法并说明算法复杂度
2012-04-24 15:13:101.维护一个k大小的小顶堆,建堆的过程复杂度为k/2*logk,之后将之后的元素每个都和堆顶元素比较,如果比堆顶元素大则替换堆顶元素之后调整堆,每次调整堆的复杂度是logk,最坏情况是之后的都一个比一个大,这时... -
堆排序
2020-03-25 23:03:01需要从大到小排序,则构建成最小堆。 2、循环删除堆顶元素,替换到二叉堆的末尾,调整堆产生新的堆顶 复杂度 空间复杂度:因为没有开辟额外的集合空间,所以复杂度为O(1) 时间复杂度 O(nlogn): 二叉堆的节点“下沉... -
剑指offer---最小的K个数(堆)
2021-01-24 19:36:36用前K个数建立最大堆,每次用堆顶元素和n-k中各个元素比较,如果堆顶元素较大,则互换位置,然后调整堆,使之重新成为最大堆。时间复杂度O(n*logk) 代码1(堆排序) import java.util.ArrayList; public class Solution... -
堆的建立&堆排序
2017-03-31 23:13:09二叉堆是一种特殊的堆,二叉堆是完全二元树或者是近似完全二元树。... 由于每次重新恢复堆的时间复杂度为O(logN),共N - 1次重新恢复堆操作,再加上前面建立堆时N / 2次向下调整,每次调整时间复杂度也为O(logN)。二次 -
剑指offer---最小的K个数(堆和partition算法两种思路解决)
2021-03-10 14:50:48题目30:最小的K个数...建一个含有K个节点的堆,由于要找的是最小的K个数,因此应该建大堆(大堆的特点就是根节点的元素是堆中的最大节点),遍历数组如果有比根节点小的元素就将其替换掉并对堆重新进行调整。 时间 -
剑指offerJZ63-数据流中位数(常见数据结构复杂度)
2020-07-12 19:58:521 对无序数组的前len(array)//2长度的元素建立最小堆,这样就得到了一个堆顶元素小于任意一个堆里的元素 2 将剩下的一半元素依次与堆顶元素比较。若比堆顶元素大,则替换之,并调整堆。(也就是说:依次遍历剩下一般... -
堆、堆排序、优先队列
2018-10-24 22:42:07堆1.1 最大堆1.2 最小堆2. 堆的逻辑结构与物理存储3. 堆的操作4. 堆的操作的复杂度5. 堆的自我调整5.1 插入节点5.2 删除节点5.3 参考实现6. 堆排序6.1 构建二叉堆6.2 堆排序过程6.3 算法步骤6.4 参考实现6.5 堆排序... -
算法题(二十六):利用堆排序解决找出最小的k个值问题
2018-11-05 20:20:29题目描述 输入n个整数,找出其中最小的K...可以用堆排序,构建有k个值的大顶堆,然后用堆头部与其他值比较,堆头部值较大则调换值,并调整,最后k个值为最小的几个。时间复杂度为nlogk。 代码 import java.util.... -
数据结构——堆
2021-01-16 20:18:18堆的实现2.1堆的向下调整算法2.2堆的构建2.2.1构造最小堆2.2.2时间复杂度分析:2.3堆的插入2.4 堆的删除,取堆顶元素,取堆的数据个数,堆的判空3.堆排序3.1 (小堆)降序 1.堆的概念 1、堆是一颗完全二叉树(适合... -
堆排序详解
2017-06-05 18:23:40堆排序是利用堆的堆序性,对于最小堆而言,最小元素在堆顶,对于一个数组先通过将其建立成一个最小堆 然后一个一个删除其堆顶元素既实现了排序。 当堆的顶部最小元素被删除后要对堆做调整使其再次满足堆序性。由于对堆... -
选择排序与堆排序
2020-02-20 11:19:37因此,想办法优化获取最小元的部分,用最小堆,于是优化为堆排序; 在排序过程中,使用最小堆需要新开辟一个数组用于存放临时拍好的部分数组,排好后再导回原始的数组输出,浪费了O(n)空间; 改进:使用最大堆... -
算法4:堆排序
2018-03-29 15:09:161.堆排序基本思想利用堆(最大堆,最小堆)进行排序,特殊的树形数据结构(完全二叉树)①将一个无序序列构造成一个堆。②输出堆顶元素后,调整剩余元素称为一个新堆。2.复杂度堆排序的主要运行时间耗费在初始构建堆...