精华内容
下载资源
问答
  • 删除堆顶元素 【堆】

    千次阅读 2018-07-16 10:07:33
    在堆中删除堆顶元素 删除元素之前先判断是否为空,如果未空则删除失败 在删除堆顶元素之后必须还是一颗完全二叉树,因为堆是由数组进行存储的所以直接删除数组的最后一个元素,不能保证还是一颗完全二叉树 因此将...

    在堆中删除堆顶元素

    删除元素之前先判断是否为空,如果未空则删除失败

    在删除堆顶元素之后必须还是一颗完全二叉树,因为堆是由数组进行存储的所以直接删除数组的最后一个元素,不能保证还是一颗完全二叉树

    因此将堆顶元素与堆尾元素交换,然后进行调整使其满足堆的约束条件

            调整思想如下:
    从根节点开始调整比较根节点值与左右孩子节点的值,
    1如果根节点值为最大值则满足条件
    2如果右孩子存在且最大值为右孩子,则将根节点与右孩子交换
    3如果左孩子存在且最大值为左孩子,则将根节点与左孩子交换
    

    上述2)3)中交换节点后还需要判断根节点右子树是否满足条件,所以需要一直往下调整,直到将最初根节点的值交换到最后一层上。

     //在堆中删除一个元素    假设是大堆
    
    105 void AdjustDown(Heap* heap, size_t size)
    106 {
    107     if(heap==NULL)
    108     {
    109         return ;
    110     }
    111     size_t child=(parent+1)*2;
    112     size_t parent=start_log;
    113 
    114     while(1)
    115     {
    116         //已经调整到了结尾必然结束
    117         if(child>=heap->size)
    118         {
    119             break;
    120         }
    121         //如果右孩子存在,且右孩子比左孩子的值大,则取孩子最大值赋给child
    122         if(child+1<heap->size && cmp(heap->data[child],heap->data[child+1])==0)
    123         {
    124             child=child+1;
    125         }
    126         //如果父节点值小于孩子中最大值,则进行交换
    127         if(cmp(heap->data[parent],heap->data[child])==0)
    128         {
    129             swap(&heap->data[parent],&heap->data[child]);
    130             parent=child;
    131             child=(parent+1)*2;
    132         }
    133         else
    134         {
    135             //如果满足
    136             break;
    137         }
    138     }
    139     return ;
    140 }
    141 
    142 void HeapErase(Heap* heap)
    143 {
    144     if(heap==NULL)
    145     {
    146         //非法输入
    147         return ;
    148     }
    149     if(heap->size==0)
    150     {
    151         //空堆无法删除
    152         return ;
    153     }
    154     //交换首尾节点的值
    155     swap(heap->data[0],heap->data[size-1]);
    156     //删掉尾节点的值
    157     --heap->size;
    158     //进行下浮调整(从根节点开始调整)
    159     AdjustDown(heap,0)
    160     return ;
    161 }  
    展开全文
  • 定义堆,封装初始化、插入、删除堆顶元素的操作;
  • 定义堆、封装初始化,插入,删除堆顶元素的操作。数据结构作业
  • 定义堆,封装初始化、插入、删除堆顶元素的操作操作 加深对于堆的理解和利用
  • C++实现最小堆及插入,调整顺序,删除堆顶元素的操作
                         

    上次用Java实现了最大堆的封装,这次就来写一下最小堆的实现吧


    插入函数的思路:
    向堆中插入元素有两种情况,一种是堆为空,那么就让插入值作为根节点即可;另一种是堆不为空,那么此时就要进行判断当前节点与其父节点的大小关系比较。此时仍有两种情况,一种是当前节点大于父节点,这样正是我们所希望的;另一种是当前节点的值小于父节点,那么就要将二者的值进行调换,然后记得更新当前节点为原来父节点的位置,而父节点的位置同样需要更新(循环正常终止的时候说明已经到了根节点,此时最小值必定为根节点)

     bool Insert(T data){        if(currentPos==MaxSize){            cout<<"Sorry , this heap is full!"<<endl;            return false;        }        currentPos++;        int targetPos=currentPos-1;        heap[targetPos]=data;        while(targetPos>0){            int parentPos=(targetPos-1)/2;            if(heap[parentPos]<heap[targetPos]){                break;            }else{                heap[targetPos]=heap[parentPos];                targetPos=parentPos;            }        }        return true;    }    //存在的bug是对根节点的大小比较,因为有可能targetPos=0而退出,此时就缺少了一次比较
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    siftDown调整过程思路:
    给定要进行调整的节点的下标,我们只需要让它和它的两个子节点中最小的那个比较即可(前提是当前节点不是叶子节点),需要注意的是要先保存当前节点的值,比较之后按大小调整顺序即可。

     void siftDown(int siftPos){        int siftPosition=siftPos;        T temp=heap[siftPosition];        int minChildPos=2*siftPosition+1;        while(minChildPos<currentPos){          //保证比较的条件成立            if((minChildPos<currentPos-1)&&(heap[minChildPos]>heap[minChildPos+1])){                minChildPos++;            }            if(temp<heap[minChildPos]){                break;            }else{                heap[siftPosition]=heap[minChildPos];                siftPosition=minChildPos;                minChildPos=2*siftPosition+1;            }        }        //作用:当要进行调换的位置不满足循环要求时,说明要进行调换的位置是叶子节点,那就不需要变换咯(这里也包括正常比较情况,可正常使用)        heap[siftPosition]=temp; }
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    删除对顶元素
    需要注意的是currentPos的大小要实时的进行更新,然后返回所删除的堆顶元素即可

     T& deleteTop(){        if(currentPos<0){            cout<<"Sorry ,this heap is empty!"<<endl;        }        T target=heap[0];        heap[0]=heap[currentPos-1];        currentPos--;        siftDown(0);        return target;    }
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    下面是完整的C++关于最小堆的实现的代码

    #include <iostream>using namespace std;template<class T>class MinHeap{    T *heap;    int MaxSize;    int currentPos;public:    MinHeap(int MS){        heap=new T[MS];        currentPos=0;        MaxSize=MS;    }    bool Insert(T data){        if(currentPos==MaxSize){            cout<<"Sorry , this heap is full!"<<endl;            return false;        }        currentPos++;        int targetPos=currentPos-1;        heap[targetPos]=data;        while(targetPos>0){            int parentPos=(targetPos-1)/2;            if(heap[parentPos]<heap[targetPos]){                break;            }else{                heap[targetPos]=heap[parentPos];                targetPos=parentPos;            }        }        return true;    }    void siftDown(int siftPos){        int siftPosition=siftPos;        T temp=heap[siftPosition];        int minChildPos=2*siftPosition+1;        while(minChildPos<currentPos){          //保证比较的条件成立            if((minChildPos<currentPos-1)&&(heap[minChildPos]>heap[minChildPos+1])){                minChildPos++;            }            if(temp<heap[minChildPos]){                break;            }else{                heap[siftPosition]=heap[minChildPos];                siftPosition=minChildPos;                minChildPos=2*siftPosition+1;            }        }        //作用:当要进行调换的位置不满足循环要求时,说明要进行调换的位置是叶子节点,那就不需要变换咯        heap[siftPosition]=temp;        ////////////////////////////////////////////    }    T& deleteTop(){        if(currentPos<0){            cout<<"Sorry ,this heap is empty!"<<endl;        }        T target=heap[0];        heap[0]=heap[currentPos-1];        currentPos--;        siftDown(0);        return target;    }};int main(){    cout << "Hello world!" << endl;    MinHeap<int> minHeap(7);    minHeap.Insert(1);    minHeap.Insert(2);    minHeap.Insert(4);    minHeap.Insert(3);    minHeap.Insert(6);    minHeap.Insert(7);    minHeap.Insert(5);    for(int i=1;i<=7;i++){        cout<<minHeap.deleteTop()<<endl;    }    return 0;}
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90

    程序运行结果如下
    程序运行结果


    总结:
    代码中存在一定得错误,出在 Insert函数中。个人认为需要对targetPos为0的特殊情况再加一层判断,估计就能解决。但是对正常添加元素还是能得到比较正常的结果的。

               

    再分享一下我老师大神的人工智能教程吧。零基础!通俗易懂!风趣幽默!还带黄段子!希望你也加入到我们人工智能的队伍中来!https://blog.csdn.net/jiangjunshow

    展开全文
  • 的结构特点 排序是一个可以高效实现排序的算法,复杂度是O(nlogn)和之前的快速排序与归并排序的复杂度相同,而它高效的排序依赖于它的结构特点 是一个完全二叉树 中每一个节点的值都必须大于等于(或者小于...

    堆的结构特点

    堆排序是一个可以高效实现排序的算法,复杂度是O(nlogn)和之前的快速排序与归并排序的复杂度相同,而它高效的排序依赖于它的结构特点

    • 堆是一个完全二叉树
    • 堆中每一个节点的值都必须大于等于(或者小于等于)其子树中每个结点的值

    第二点是说明每个节点都必须大于等于(或者小于等于)其左右子结点的值。

    其中大于等于其左右节点的堆叫大顶堆,小于等于其左右节点的堆叫小顶堆

    堆的存储结构分析

    由于堆是一个完全二叉树,所以它可以用非常简便的数组来进行存储。

    数组存储的元素就是节点的值,而数组下标位置就代表着该结点在堆中的位置

    img

    由此我们可以得出一个与下面算法实现息息相关的结论

    如果某一个结点存储时在数组中下标为i

    • 它的父节点位置在i/2
    • 它的左子结点位置在2i
    • 它的右子结点位置在2i+1

    堆的相关算法

    插入元素

    过程思路

    在数组末尾插入元素,再判断是否符合堆的特点,即是否小于父节点,如果不小于,跟父节点交换,交换直到小于父节点。这个过程称为堆化,且是过程是自下而上

    img
    代码实现
    void insert_node(int a[],int val,int cnt)
    {
        int i=(cnt+1)/2;	//也可以只用一个变量i
        int j = cnt+1;
        a[j] = val;			//a[cnt+1]=val
        while(a[i]<a[j] && i>0)	//    while(a[i/2]<a[i] && i/2>0)
        {
            swap(a,j,i);			//swap(a,i,i/2)
            i = i / 2;
            j = j / 2;
        }
    }
    void swap(int a[], int m, int i)
    {
        int temp = a[i];
        a[i] = a[m];
        a[m] = temp;
    
    }
    

    删除堆顶元素

    过程思路

    删除一个元素,由于堆的完全二叉树的特点限制,要提防出现最后一层断层,即不连续。

    img

    所以采用的方法是把最末的元素替换堆顶再进行堆化,这样得到的新堆肯定是符合其自身特点的。很明显,这里是从上往下的堆化过程。

    img
    代码实现
    void heaping_(int a[],int cnt,int i)    //一次该函数调用,可以把堆从i结点开始到堆底的全部堆化
    {
        while (true)
        {
            int maxpos = i;              
            if(a[2 * i] > a[maxpos]&& 2 * i <= cnt)maxpos = 2 * i;  //是否左节点会大于该节点
            if (a[2 * i + 1] > a[maxpos] && 2 * i <= cnt)maxpos = 2 * i + 1;    //是否右节点会大于该节点/左节点,注意这里是maxpos不是i因为右节点可能会大于左节点,
            if(i==maxpos)break;         //如果该节点大于左节点又大于右节点,说明不需要交换堆化跳出循环,
            swap(a,maxpos,i);          //把三个结点中最大的那个,换到结点位置
            i = maxpos;                
        }
    }
    void delete_node(int a[],int cnt)
    {
        if(cnt==0)
        {
            return;
        }
        a[1] = a[cnt + 1];
        cnt--;
        heaping_(a, cnt, 1);
    
    }
    

    堆排序

    过程思路

    堆排序分为两个步骤

    • 建堆
    • 排序

    为什么会需要建堆呢,因为排序的时候的算法利用了堆的特点,建堆是通过对已经有的数组进行堆化,使数组满足堆的特点。这里采用的是:从最后一个非叶子结点——>也就是数组有效元素/2位置 开始堆化(叶子节点不需要堆化,)

    排序的思想是每次都将大顶堆堆顶元素放在数组末尾,再对数组里n-2个元素进行堆化,多次进行直到把倒数第二个元素进行交换,堆化。

    代码实现
    void build_heap(int a[],int cnt)    //采用的方法是从下往上依次堆化
    {
        int i;
        int maxpos;
        for (i = cnt / 2; i>0;i--)
        {
            heaping_(a,cnt,i);
        }
    }
    void sort_heap(int a[], int cnt)
    {
        int i = cnt;
        while (i > 1)
        {
            swap(a, 1, i);
            i--;
            heaping_(a, i, 1);
        }
    }
    

    完整代码

    #include <stdio.h>
    #include <stdbool.h>
    #include <windows.h>
    #include <malloc.h>
    int cnt;
    void heaping_(int a[], int cnt, int i);
    void build_heap(int a[],int cnt);       //大顶堆
    void sort_heap(int a[],int );             //堆排序
    void insert_node(int a[],int val,int cnt);  //插入一个元素
    void delete_node(int a[],int cnt); //删除堆顶元素
    void swap(int a[], int m, int n);
    void print_node(int a[],int cnt)
    {
        int i;
        for (i = 1; i <=cnt; i++)
        {
            printf("%d  ", a[i]);
        }
    }
    
    int main()
    {
        int cnt = 8;
        int heap[10] ={0,7,5,19,8,4,1,20,13};
        build_heap(heap,cnt);
        print_node(heap,cnt);
        printf("\n");
        //插入
        printf("after inserting:");
        printf("\n");
        insert_node(heap, 27, cnt);
        print_node(heap, cnt);
        //删除
        printf("\n");
        printf("after deleting");
        delete_node(heap, cnt);
        cnt--;
        printf("\n");
        print_node(heap, cnt);
       //堆排序
        printf("\n");
        printf("after sorting");
        printf("\n");
        sort_heap(heap, cnt);
        print_node(heap, cnt);
    
    }
    
    void heaping_(int a[],int cnt,int i)    //一次该函数调用,可以把堆从i结点开始到堆底的全部堆化
    {
        while (true)
        {
            int maxpos = i;
            if (2 * i <= cnt && a[2 * i] > a[i])
                maxpos = 2 * i;                                                 //是否左节点会大于该节点
            if (2 * i +1<= cnt && a[2 * i + 1] > a[maxpos])
                maxpos = 2 * i + 1;     //是否右节点会大于该节点/左节点,注意这里是maxpos不是i因为右节点可能会大于左节点,
            if(i==maxpos)break;         //如果该节X点大于左节点又大于右节点,说明不需要交换堆化跳出循环,
            swap(a,maxpos,i);          //把三个结点中最大的那个,换到结点位置
            i = maxpos;                
        }
    }
    void build_heap(int a[],int cnt)    //采用的方法是从下往上依次堆化
    {
        int i;
        int maxpos;
        for (i = cnt / 2; i>0;i--)
        {
            heaping_(a,cnt,i);
        }
    }
    void sort_heap(int a[], int cnt)
    {
        int i = cnt;
        while (i > 1)
        {
            swap(a, 1, i);
            i--;
            heaping_(a, i, 1);
        }
    }
    
    void swap(int a[], int m, int i)
    {
        int temp = a[i];
        a[i] = a[m];
        a[m] = temp;
    
    }
    void insert_node(int a[],int val,int cnt)
    {
        int i=cnt+1;
        a[i] = val;
        while(a[i]>a[i/2] && i/2>0)
        {
            swap(a,i,i/2);
            i = i / 2;
        }
    }
    void delete_node(int a[],int cnt)
    {
        if(cnt==0)
        {
            return;
        }
        a[1] = a[cnt];
        cnt--;
        heaping_(a, cnt, 1);
    }
    
    

    运行结果如下
    在这里插入图片描述

    总结

    • 堆的存储结构是利用数组,关系是通过下标来反映
    • 堆的算法跟堆的特性和下标有很大的关系,需要从这两个点去思考编程
    • 堆化的方法分为两种,删除和建堆的自上而下堆化方法 和 插入元素自下而上的堆化方法。
    展开全文
  • class MaxHeap { int* h; int currentsize; int maxsize; public: MaxHeap(int *a,int n,int max); void BuildHeap(); void siftdown(int i); void siftup(int i); void delettop();... void show()
  • /* *将堆中元素存储在数组里,输出堆中元素也就是...*除堆顶元素 */ #include using namespace std; class Heap { private:  int *data, size; public:  Heap(int length_input) {  data = new int[le
    /*
    *将堆中元素存储在数组里,输出堆中元素也就是输出数组里的元素,并获取和删
    *除堆顶元素
    */


    #include<iostream>
    using namespace std;
    class Heap {
    private:
        int *data, size;
    public:
        Heap(int length_input) {
            data = new int[length_input];
            size = 0;
        }
        ~Heap() {
            delete[] data;
        }
        void push(int value) {
            data[size] = value;
            int current = size;
            int father = (current - 1) / 2;
            while (data[current] > data[father]) {
                swap(data[current], data[father]);
                current = father;
                father = (current - 1) / 2;
            }
            size++;
        }
        //输出堆中元素
        void output() {
            for (int i = 0; i < size; i++) {
                cout << data[i] << " ";
            }
            cout << endl;
        }
        //获取堆顶元素,即data[0]
        int top() {
            return data[0];
        }
        
        //下滤操作的调整策略:当前元素和左右两个孩子比较大小,如果两个孩子权值较大者,比当前元素权值大,
        //则将该孩子和当前元素进行交换,如果此时仍不满足堆序性,则调用update函数对该孩子继续进行堆调整
        //pos:当前调整位置, n:当前堆中元素个数
        void update(int pos, int n) {
            int lchild = 2 * pos + 1, rchild = 2 * pos + 2;//等于当前元素的左、右孩子位置
            int max_value = pos;
            if (lchild < n && data[lchild] > data[max_value]) {
                max_value = lchild;
            }
            if (rchild < n && data[rchild] > data[max_value]) {
                max_value = rchild;
            }
            if (max_value != pos) {
                swap(data[pos], data[max_value]);
                update(max_value, n);
            }
        }
        
        
        //删除堆顶元素
        //方法:将堆顶元素和对的最后一个元素进行交换, 然后对堆顶元素做一个自上而下的堆调整,即下滤操作。
        void pop() {
            swap(data[0], data[size - 1]);
            size--;
            update(0, size);
        }
        
    };
    int main() {
        int arr[10] = { 12, 9, 30, 24, 30, 4, 55, 64, 22, 37 };
        Heap heap(100);
        for (int i = 0; i < 10; i++) {
            heap.push(arr[i]);
        }
        heap.output();
        cout << heap.top() << endl;
        heap.pop();
        heap.output();
        return 0;
    }
    展开全文
  • : (1)通常是一个可以被看做一棵树的数组对象。 (2)将根节点最大的叫做最大或...(1)n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时,称之为。 (ki<= k2i,ki<= k2i+1)或者(ki>= ...
  • 【题目】【0、2、1、4、3、9、5、8、6、7】是以数组形式存储的最小堆,删除堆顶元素0后的结果是()。  A、【2、1、4、3、9、5、8、6、7】  B、【1、2、5、4、3、9、8、6、7】  C、【2、3、1、4、7、9、5、8、6】...
  • 1.【题目】【0、2、1、4、3、9、5、8、6、7】是以数组形式存储的最小堆,删除堆顶元素0后的结果是()。  A、【2、1、4、3、9、5、8、6、7】  B、【1、2、5、4、3、9、8、6、7】  C、【2、3、1、4、7、9、5、8、6...
  • 6-1 最小堆插入元素和删除堆顶(无哨兵元素) (20分) 对于给定的最小堆(优先队列),分别实现插入元素和删除堆顶的函数。 函数接口定义: int insertIntoHeap... //将堆顶元素拷贝到pElement所指变量并删除堆...
  • PTA 最小堆插入元素和删除堆顶(无哨兵元素) (20分) 对于给定的最小堆(优先队列),分别实现插入元素和删除堆顶的函数。 函数接口定义: int insertIntoHeap... //将堆顶元素拷贝到pElement所指变量并删除堆...
  • 删除堆顶:将数组最后一个元素替换堆顶,然后向下渗透。 头文件MaxHeap.h #ifndef _MAX_HEAP_ #define _MAX_HEAP_ template <class T> class MaxHeap { public: MaxHeap(int mx = 10); //默认堆的最大值为10...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 538
精华内容 215
关键字:

删除堆顶元素