精华内容
下载资源
问答
  • 从堆中删除任意元素
    千次阅读
    2016-10-11 16:40:02

    算法导论6.5-8

    def heapDelete(A, i):
        A[i], A[-1] = A[-1], A[i]
        A.pop()
        maxHeap(A, i)

    上面这个算法是错误的,因为没有考虑如果替换元素比被替换元素的值更大,那么有可能i的父节点也不能保持最大堆性质的情况。如图,要删除1,用6替换1,3不再保持最大堆性质。

            10
           /   \
          9     3
        /   \  /  \
       8    5  1   2
      / \
     7   6

    修改后的版本

    def heapDelete(A, i):
        t = A.pop()
        if A[i] < t:
            # A[i]节点保持最大堆性质,但是A[i]的父节点可能最大堆性质不再保持
            heapIncreaseKey(A, i, t)
        else:
            # A[i]父节点保持最大堆性质,但是A[i]的最大堆性质可能不在保持
            A[i] = t
            maxHeapify(A, i)
    更多相关内容
  • 排序,删除堆中任意单一元素

    千次阅读 2022-03-13 18:29:06
    package headSort; import java.util.Arrays; public class MyHeap { public int[] arr; public int size; public MyHeap(int[] arr) { this.arr = arr;... * 删除下标为i的元素 ...将最大元素删除->让删除元素
    package headSort;
    import java.util.Arrays;
    public class MyHeap {
        public int[] arr;
        public int size;
        public MyHeap(int[] arr) {
            this.arr = arr;
            this.size=arr.length;
        }
        /**
         * 删除下标为i的元素
         * 思路->将最大元素删除->让删除元素的值增加到原先的最大元素->替换思想
         */
        public void delete(int i){
            int deleteValue = arr[i];
            int pop = pop();
            if (i!=0)        increaseValue(arr,deleteValue,pop);
        }
        public int pop(){
            int popValue = arr[0];
            swap(arr,0,arr.length-1);
            size--;
            arr=Arrays.copyOf(arr,size);
            headify(0, size);
            return popValue;
        }
        private void increaseValue(int[] a,int deleteValue,int k){
            // 一定是变大
            int i = 0 ;
            while (arr[i]!=deleteValue) i++;
            arr[i]=k;
            // 上浮
            int parentIndex;
            while ((parentIndex=parent(i)) >= 0 && a[i]>a[parentIndex]){
                swap(a,parentIndex,i);
                i=parentIndex;
            }
        }
        public void headSort() {
            for (int i = (size - 1) / 2 ; i >= 0; i--)
                headify(i,size);//为什么这个时候length不用-1 ->因为这个时候需要全部节点都要考虑
    
            for (int i = size - 1; i >= 0; i--) {
                swap(arr, i, 0);//将第一元素移动到最后->堆顶元素是最大元素->这样一来就不用管最后的元素了,排序从后往前排
                //为什么这个时候不用考虑最后一个节点->因为这个时候最后一个节点已经有序了不用管了
                headify(0,i);
            }
        }
        private void headify (int i,int length) {
            int largest = i;
            int leftson = 2 * i + 1;
            int rightson = 2 * i + 2;
            if (leftson < length) largest = (arr[largest] > arr[leftson]) ? largest : leftson;
            if (rightson < length) largest = (arr[largest] > arr[rightson]) ? largest : rightson;
            if (largest != i) { //largest是更最大值交换的位置
                swap(arr,largest,i);
                headify(largest,length);
            }
        }
        private void swap(int[] a, int i, int j) {
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
        public void print_ln(){
            for (int i = 0 ; i < size ; i ++){
                if (i==0) {System.out.print(" [ " + arr[i] + "  ");continue;}
                if (i == size - 1){
                    System.out.println( arr[i]  + " ] ");
                    break;
                }
                System.out.print( arr[i] + "  ");
            }
        }
        private int parent(int i){
            return (i%2==0)?i/2-1:i/2;
        }
        public static void main(String[] args) {
            MyHeap myHeap = new MyHeap(new int[]{10, 9, 3, 8, 5, 1, 2, 7, 6});
            myHeap.delete(2);
            myHeap.print_ln();
            myHeap.headSort();
            myHeap.print_ln();
        }
    }
    
    
    展开全文
  • 代码1:转载于... struct heap {//手写实现删除任意位置数值的 priority_queue<int> A , B; //A存储了当前所有元素(包括未删除元素), //Bq2q2存储了q1q1已删除的元素 ...

    代码1:转载于https://blog.csdn.net/weixin_45630722/article/details/108286961

    struct heap {//手写实现删除任意位置数值的堆
        priority_queue<int> A , B;   //A存储了当前所有元素(包括未删除元素),

                                                     //Bq2q2 存储了 q1q1 中已删除的元素
        void push(int x) {
            A.push(x);
        }
        
        void erase(int x) {
            B.push(x);
        }
        
        void pop() {
            while(B.size() && A.top() == B.top()) A.pop(), B.pop();
            A.pop();
        }
        
        int top() {
            while(B.size() && A.top() == B.top()) A.pop(), B.pop();
            if(!A.size()) return 0;
            return A.top();
        }
        
        int size() {
            return A.size() - B,size();
        }
        
        int stop() {
            if(size() <  2) return 0;
            int x = top(); pop();
            int y = top(); push(x);
            return y;        
        }
    } ALL, First[110000], Second[110000];

    代码2(转载于https://www.cnblogs.com/Judge/p/10557516.html

    支持删除任意元素以及一些其他基本操作的堆

    阅读目录(Content)

    安利一个黑科技,不知道是谁发明的(好像也有些年代了?)

    其实这个黑科技的本质就是一个大根堆,不同的是 它支持删除堆内任意元素,同时也支持堆的基本操作

    code

    代码如下:

    struct Heap{ priority_queue<int> q1,q2;
    	inline void push(int x){q1.push(x);}
    	inline void erase(int x){q2.push(x);}
    	inline void pop(){for(;q2.size()&&q1.top()==q2.top();q1.pop(),q2.pop());if(q1.size())q1.pop();}
    	inline int top(){for(;q2.size()&&q1.top()==q2.top();q1.pop(),q2.pop());return q1.top();}
    	inline int top2(){int val,ret; val=top(),pop(),ret=top(),push(val); return ret;}
    	inline int size(){return q1.size()-q2.size();}
    };

    结构介绍

    解释一下两个堆 q1q1 和 q2q2 :

    q1

    q1q1 存储了当前所有元素(包括未删除元素)

    q2

    q2q2 存储了 q1q1 中已删除的元素

    操作介绍

    push

    我们看到 push 操作,很平常,就是向 q1q1 中 pushpush 一个新的元素

    erase

    这就是这个黑科技的精华了,我们向 q2q2 中 pushpush 一个元素表示在 q1q1 中它已经被删除了

    pop

    这里就要用到 q2q2 里面的元素了,如果堆顶的元素已经被 eraseerase 过,那么它此时应该在 q2q2 中的堆顶

    此时我们把两个堆一起 poppop 就好了,直到堆顶元素不同或者 q2q2 没元素了

    top

    这里就是先进行和 poppop 中类似的操作,删除已经 eraseerase 的元素,然后取出堆顶

    top2

    有点骚,这个操作可以取出堆中的次大值,而 top3top3 、top4top4 以此类推(虽说不怎么用到)

    size

    这个就是返回堆大小的,可以知道堆当前真实大小就是 q1q1 大小减去 q2q2 大小

    总结

    新技能 getget !

    但是注意一下,这里我们的 eraseerase 操作必须合法, 否则会出现 bugbug

    或者修改一下操作可能可以支持不合法操作...但我本人觉得不大可能...

     

    展开全文
  • 最小两个基本功能实现

    堆是一种特殊的完全二叉树,分为最小堆和最大堆。

    最小堆的每个父节点的值小于子节点。最大堆反之。

    这里我们用数组实现最小堆。

    ps:完全二叉树 若共有n个节点,则高度为 (log2 n)+1

    代码最下面有数据可输入验证。

    代码中 shiftup函数 为建立最小堆或向最小堆中插入元素(不删除原有元素),插入在叶节点

    建立n个节点 的时间复杂度为O(nlogn)

    代码中 shiftdown函数是在最小堆上进行的操作,为删除最小元素并插入新的元素,插入在根节点。

    一次的时间复杂度为O(logn) 下面代码只执行了一次

    n次的话就是O(nlogn)  (废话)

    #include <iostream>
    #include <algorithm>
    using namespace std;
    int n=0;
    int h[10000];
    void siftup(int i);  // i都是在树中的编号。
    void siftdown(int i);//
    int main (){
        int i;
        for(i=1;i<=9;i++){
            n++;            //n表示堆中元素的个数。
            scanf("%d",&h[n]);//输入新的元素并调整其在最小堆中的位置
            siftup(n);
        }
        cout<<h[1]<<endl;    //输出值最小的元素
        scanf("%d",&h[1]);  //删除值最小的元素并插入新的元素 
        siftdown(1);      //元素首先插入到编号为1的位置,后向下调整到合适位置。
        cout<<h[1]<<endl;  //输出新的值最小的元素
        for(i=1;i<=9;i++){  //输出堆中存储的元素
            if(i>1)cout<<" ";
            cout<<h[i];
        }
        return 0;
    }
    
    //建立最小堆(向堆中插入元素,这里是插入在叶节点)。   //元素从树底不断向上走  
    void siftup(int i){//i表示当前待调整的元素在树中的编号。
        int flag=0;
        if(i==1)return ;    //如果是1号节点就不再向上调整。
        while(flag==0&&i!=1){
            if(h[i]<h[i/2]){
                swap(h[i],h[i/2]); 
                i/=2;      //元素调整后新的编号
            }else{
                flag=1;     //结束调整
            } 
        }
        return ;
    }
    
    //插入一个新的元素在树顶(删除掉了原有的树顶元素,此时树顶为空),并调整其位置
    //元素从树顶不断向下走
    void siftdown(int i){   //i为1,即新插入的元素在树中编号为1。
        int flag=0;
        int t;
        while(i*2<=n&&flag==0){  //i*2<=n表示至少存在左子节点。
            if(h[i]>h[i*2]){
                t=i*2;
            }else{
                t=i;
            }
            if(i*2+1<=n&&h[t]>h[i*2+1]){
                t=i*2+1;
            }
            //上面两个对t的改变, 表示找出父节点与两个子节点中最小的                            
            if(t==i){            //并将其交换到父节点的位置。
                flag=1;        //结束调整。
            }else{
                swap(h[i],h[t]);
                i=t;
            }
        }
        return ;
    }
    // 2 7 5 19 22 17 3 12 36   100  //输入
    // 2                              //第一行输出,表示原有最小值元素
    // 3                              //第二行输出,表示新的最小值元素
    // 3 7 5 12 22 17 100 19 36       //对堆中存储的元素输出

    一种O(n)时间复杂度建堆qwq

    完全二叉树的最大非叶节点为n/2  (总n是节点个数)

    同样代码下面有样例输入输出验证

    #include <iostream>
    using namespace std;
    int h[10000];
    int n;                 //这个siftdown跟上面那个代码的siftdown一模一样
    void siftdown(int i){  //一次siftdown作用为 使以i为根节点的子树符合最小堆性质
        int flag=0;         //【(传i的时候保证以i*2和i*2+1为根节点的子树符合
        int t;                //最小堆的性质)】,i从下往上,从右到左,有点dp的意思
        while(flag==0&&i*2<=n){  //叶节点就一个点 符合【  】的性质,所以从最大非叶节点开始
            t=i;                     //即n/2
            if(h[i*2]<h[i]){
                t=i*2;
            }
            if(i*2+1<=n&&h[i*2+1]<h[t]){
                t=i*2+1;
            }
            if(i==t)flag=1;
            else{
                swap(h[i],h[t]);
                i=t;
            }
        }
        return ;
    }
    int main (){
        cin>>n;
        int i;
        for(i=1;i<=n;i++){
            cin>>h[i];
        }
        for(i=n/2;i>=1;i--){
            siftdown(i);
        }
        for(i=1;i<=n;i++){
            if(i>1)cout<<" ";
            cout<<h[i];
        }
        return 0;
    }
    /*
    14 
    99 5 36 7 22 17 92 12 2 19 25 28 1 46  //输入
    1 2 17 5 19 28 46 12 7 22 25 99 36 92  //输出
    */

    展开全文
  • 数据结构 C++ 最大(大根)插入、删除、查找任意元素
  • 最小的指定删除

    千次阅读 2020-05-23 23:51:58
    其实最小是可以指定删除某个节点的,包括最大。只要使用正确的方法 伪代码: // 向下调整 if (末尾节点key >要删除的节点key) { //这里就使用尾换头的方法调整,只不过把所谓的 "头" 换成了指定节点 } // ...
  • 11、删除操作(中篇)

    千次阅读 2019-03-30 23:19:56
    一、删除操作的简单思路 1、首先我们判断是不是为空,然后获取我们的元素,和我们的...因为得定义,比如最大,就是堆中任意节点都会下于等于它的父亲节点。我们第一个元素,必须进行和它的孩子节点...
  • 数据结构之

    万次阅读 2020-07-01 10:33:38
    思考 假如需要设计一种数据结构,用来存放整数,要求提供3个接口: 添加元素 获取最大值 删除最大值 如果使用动态数组、双向链表和二叉树实现这个数据结构对应的时间复杂度...使用,可以使得获取最大值的时间复杂
  • 最大(创建、删除、插入和排序)图文详解

    千次阅读 多人点赞 2020-08-21 10:33:03
    注意区分选择树,因为选择树(selection tree)概念和最小有些类似,他们都有一个特点是“树的根结点都表示树的最小元素结点”。同理最大的根结点是树中元素最大的。那么来看具体的看一下它长什么样?(最小
  • 定义:n个关键字序列称为,当且仅当该序列满足下列两个条件的一个: L(i)⩽L(2i)且L(i)⩽L(2i+1)L(i)\leqslant L(2i)且L(i)\leqslant L(2i+1)L(i)⩽L(2i)且L(i)⩽L(2i+1) ① 小根 L(i)⩾L(2i)且L(i)⩾L(2i+1...
  • 优先队列和特别适合找第k大、K小的特殊数据结构 翻转链表: 203 445 92 需要两个指针,前指针和当前指针 nxt=cur.next cur.next=pre pre=cur cur=nxt 优先队列和特别适合找第k大、K小的特殊数据结构...
  • 我们可以利用这个特性,保存两个priority_queue,一个是数据,一个是待删除数据,当两个priority_queue 的 top() 元素相同的时候,我们再删除两个优先队列的 top。 实现 升序优先队列 实现代码...
  • 结构是一种优先队列,可以以任意顺序添加对象,并随时查找或删除最小(大)的元素,或者查找和删除前 K 个最小(大)元素。相比于列表方法min() / max(),这样做的效率要高得多。 结构是一种特殊的完全二叉树...
  • 二叉类添加和删除元素

    千次阅读 2010-05-22 19:26:00
     二叉 在有序列表,每个元素都按照由低到高或由高到低的顺序保存在恰当的位置。这很有用,但是还 不够。事实上,我们并不关心数字 127 是否比 128 在更低的位置上。我们只是想让 值最低的元素能放在列表顶端...
  • 的插入、删除操作几个基本操作的插入删除 感谢简书[唐先僧]的博文数据结构:(Heap),本博文有部分借鉴内容。 的介绍 是一个有固定顺序的完全二叉树,通常用数组来表示。 用数组表示,如何区分父...
  • 最大的插入和删除

    千次阅读 2020-03-23 00:38:43
    首先,我们要了解这种数据结构,这里的具有完全二叉树的结构,并且某个节点的值总是不大于或不小于其孩子节点的值(‘不大于’的情况叫最小,‘不小于的情况叫最大’),每个节点的子树都是树...
  • 相关操作复杂度分析

    千次阅读 2021-04-06 09:32:41
    的层数 通常用一颗完全二叉树组成 那么n个结点的完全二叉树有log2(n+1)层,近似等于log2n 解释一下为什么log2n层? 第一层2^0个元素 第二层2^1个元素 第三层2^2个元素 第h层2^(h-1)个元素 等比数列求和公式:2^0+ ...
  • 【数据结构】最大的插入与删除

    千次阅读 2017-05-23 21:45:00
    是一种特殊的队列,从堆中取出元素的顺序不是按照元素进入队列的先后顺序,而是依据元素的优先权,或者说是大小,所以也叫做“优先队列”。 最常使用二叉树结构表示,可以看作是一种特殊的完全二叉树,对于一...
  • 排序怎么实现的 怎么插入新元素 时间复杂度
  • 数据结构之优先级队列【】(Heap)

    千次阅读 多人点赞 2022-07-15 14:51:31
    (1)优先级队列底层是来实现的 (2)的本质是完全二叉树 ,有大根和小根 (3)大根:根节点最大的; 小根:根节点最小的 (6)top-K问题:前K个最大的元素建小根;...核心思想:堆元素删除...
  • 堆,建堆,堆排序,堆删除和堆插入

    万次阅读 多人点赞 2018-05-24 23:42:45
    注意:看这篇文章之前,你一定要知道完全二叉树的结构首先要明白一点,是一种数据结构,和队列,链表,树等等一个级别。的定义是一棵节点含有...堆中任意节点为根节点的子树仍然是的分类最大(大...
  • 的性质、的实现、排序

    千次阅读 2020-11-28 19:28:18
    3. 删除堆元素 4. 其他操作 5. 完整代码 三、排序 1. 原地建 2. 排序 3. 完整代码 4. 建的复杂度:O(n) 5. 排序的复杂度:O(nlogn) 6. 和快速排序的比较 一、的性质 是一种特殊的树。 ...
  • 是一种特殊的“队列”,它取出元素的顺序是依照元素的优先级大小,而不是元素进入...根据最小的结构特性,本文使用含有哨兵元素的数组实现了最小的创建、插入和删除。 数据类型定义和函数声明 #include #
  • 排序C语言实现详解

    千次阅读 2020-01-15 18:01:46
    2、删除堆元素 三、的应用 1、排序 1、建 2、排序 2、优先级队列 3、求 Top K 4、求位数 四、C语言实现 1、数据结构 2、操作函数声明 3、具体实现 4、调试问题 五、说明 一、 这里的...
  • 的创建,插入,删除,建立

    万次阅读 多人点赞 2018-10-23 11:18:49
    什么是 优先队列( (Priority Queue ):特殊的“ 队列” ,取出元素的顺序是依照元素的 优先权(关键字)。 大小,而不是元素进入队列的先后顺序。 优先队列的完全二叉树示 的两个特性 结构性 :用数组表示的...
  • 的创建以及的基本操作

    千次阅读 2021-12-05 21:09:50
    特性:顶元素是所有元素中最大(小)的 任意节点都比其孩子节点大(小) 从堆顶到所有叶子路径中是降序(升序) 三、的相关操作 1.创建 头文件: #pragma once #include<stdio.h> #include&.....
  • 数据结构:手写

    2022-02-16 19:44:27
    (heap)是计算机科学一类特殊的数据结构的统称。通常是一个可以被看做一棵树的数组对象。总是满足下列性质: 1.堆中某个节点的值总是不大于或不小于其父节点的值;...4.删除任意一个元素。 ..
  • 因为数组结构是连续的内村地址,所以数组全部或者部分元素被连续被存在CPU缓存里面,而链表的节点是分散在空间里面的,这时候CPU缓存帮不上忙,只能是去读取内存,而缓存的速率要比内存快。 3、CPU --》寄存器–》...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 68,610
精华内容 27,444
热门标签
关键字:

从堆中删除任意元素

友情链接: Neighbor.rar