精华内容
下载资源
问答
  • 创建的方式有两种,一种是一边插入结点,一边调用的插入方法调整堆,这样的时间复杂度就是 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 +
                    '}';
        }
    }
    
    
    展开全文
  • 排序思想:排序,利用这种数据结构设计的一种排序...将顶元素与末尾元素进行交换,使末尾元素最大/最小,则末尾就是排好序的数组。然后继续调整堆为大顶堆/小顶堆。再将顶元素与末尾元素交换,得到第二大...

    e7c5677de006ecf9f921d230f7151cc0.png

    堆排序思想:

    • 堆排序,利用堆这种数据结构设计的一种排序算法,是选择排序的一种。
    • 堆是一种近似完全二叉树的数据结构,并且:子节点的键值或索引总是小于(或者大于)它的父节点。

    算法描述:

    • 构造初始堆。将给定无序序列构造成一个堆(一般升序采用大顶堆,降序采用小顶堆);
    • 将堆顶元素与末尾元素进行交换,使末尾元素最大/最小,则末尾就是排好序的数组。
    • 然后继续调整堆为大顶堆/小顶堆。
    • 再将堆顶元素与末尾元素交换,得到第二大元素;
    • 重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素;
    • 如此反复进行交换、重建、交换,直到整个序列有序。

    f7edf67d60567bcceafe6fc5fd82b5a1.gif

    参考:

    • https://zhuanlan.zhihu.com/p/73714165
    • https://zhuanlan.zhihu.com/p/142673431
    • 南风以南:python实现·十大排序算法之堆排序(Heap Sort)

    我的理解之大白话:

    好不容易看懂了,咱必须得唠唠,(害,写的啥玩意,感觉语句不通的):

    1. 首先,堆,大顶堆,小顶堆的定义都很明显。下图里左右分别为大顶堆和小顶堆。

    de97cf88043c19bd7f98cf7b3f5f05bb.png
    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],我们先给他画成树的形式。如下图,而我们的目标是把他转化为大顶堆。

    31c3008a7cad6d835bac6491acf3bd7b.png
    • 我怎么把给序列的一般树排序成大顶堆呢?
      • 这就是堆排序算法里的重点了,我们将问题拆解,根据堆关于父子节点数值问题的定义,其实这个树可以拆解为众多的 父节点和子节点 组,比如上图,基本单位就是[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:排序算法稳定性的判定

    • 稳定:如果
      原本在
      前面,而
      ,排序之后
      仍然在
      的前面。
    • 不稳定:如果
      原本在
      的前面,而
      ,排序之后
      可能会出现在
      的后面。

    至于时间复杂度怎么算的:放过我吧老天爷啊啊啊啊啊

    展开全文
  • 堆排序算法是建立在二叉树的堆结构上的,通过交换堆(一维数组)中的元素,并进行上浮或下沉函数运算实现多次调整 堆排序算法的复杂度低,和快速排序属于相同速度级别的一种快速的排序算法 下面以最小堆
    原文地址为:堆排序 两种实现(最小堆和最大堆)

    堆排序算法是建立在二叉树的堆结构上的,通过交换堆(一维数组)中的元素,并进行上浮或下沉函数运算实现多次调整

    堆排序算法的复杂度低,和快速排序属于相同速度级别的一种快速的排序算法

    下面以最小堆和最大堆来进行堆排序算法的实现,具体内容在代码中进行讲解


    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;
    }
    


    展开全文
  • * 堆的插入(插入到堆尾,再自下向上调整最小堆) * 堆的删除(删除堆顶元素并用堆尾元素添补,再自上向下调整最小堆) * 堆排序(时间复杂度:O(nlgn),空间复杂度O(1),不稳定):升序排序一般用最大
  • 本文以最小堆为例,构建堆的过程是首先初始化一个数组a,其中a[0]存数组的长度n,即第一个有效元素从a[1]开始,这样保证左孩子为2*i,右孩子为2*I+1;然后从(n - 1)/2开始,每次向下调整一个元素,直到n = 0。 ...
  • 定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。 注意:保证测试中不会当栈为空的时候,对栈调用pop()或者min()或者top()方法。 解答: class Solut...
  • c语言最小堆的实现-优先队列

    千次阅读 2017-02-25 15:07:48
    libevent 中有定时事件的管理,用户可以把超时的定时事件插入到 管理器...查看了源码发现,定时器的数据结构其实是由最小堆来实现的。 优先队列为完全二叉树,所以在插入调整的时间复杂度为 O(N),弹出的复杂度为O(1);
  • 思路:建一个大小为k的堆,堆中的每个元素代表一个List,元素的key为List当前最小元素的值,调整最小堆,取出堆顶的元素,并记录到排序结果中,然后插入相应List中下一个元素的值作为新的堆顶元素key的值,然后...
  • 堆作为一种特殊的数据结构,它的排序也非常有意思。和冒泡排序、选择排序一样,他们都能求出顺序表的第n大的数据。...交换堆顶的元素和最后一个元素,此时最后一个位置作为有序区,然后进行其他无序区的堆调整,重...
  • 思路:用数组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...
  • 1.维护一个k大小的小顶堆,建的过程复杂度为k/2*logk,之后将之后的元素每个都和顶元素比较,如果比顶元素大则替换顶元素之后调整堆,每次调整堆复杂度是logk,最坏情况是之后的都一个比一个大,这时...
  • 排序

    2020-03-25 23:03:01
    需要从大到小排序,则构建成最小堆。 2、循环删除堆顶元素,替换到二叉堆的末尾,调整堆产生新的堆顶 复杂度 空间复杂度:因为没有开辟额外的集合空间,所以复杂度为O(1) 时间复杂度 O(nlogn): 二叉堆的节点“下沉...
  • 用前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)。二次
  • 题目30:最小的K个数...建一个含有K个节点的,由于要找的是最小的K个数,因此应该建大(大的特点就是根节点的元素是中的最大节点),遍历数组如果有比根节点小的元素就将其替换掉并对重新进行调整。 时间
  • 1 对无序数组的前len(array)//2长度的元素建立最小堆,这样就得到了一个堆顶元素小于任意一个堆里的元素 2 将剩下的一半元素依次与堆顶元素比较。若比堆顶元素大,则替换之,并调整堆。(也就是说:依次遍历剩下一般...
  • 堆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 堆排序...
  • 题目描述 输入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:16
    1.堆排序基本思想利用堆(最大堆,最小堆)进行排序,特殊的树形数据结构(完全二叉树)①将一个无序序列构造成一个堆。②输出堆顶元素后,调整剩余元素称为一个新堆。2.复杂度堆排序的主要运行时间耗费在初始构建堆...

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 199
精华内容 79
关键字:

最小堆调整复杂度