Maple's Blog.

堆(最大堆)

算法与数据结构
字数统计: 1.3k阅读时长: 6 min
2019/07/10 Share

######”ArraY.h”头文件：

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include<iostream>
#include<cmath>
#include<cassert>
#include<cstdlib>
#include<cstring>
using namespace std;
template<typename T>
class Array{
private:
    T *data;         //数组名
    int size;         //数组中元素的个数
    int Capacity;    //数组容量
public:
    Array(int Capacity){
        data=new T [Capacity];
        this->size=0;
        this->Capacity=Capacity;
    }

    Array(T arr[],int n){
        data=new T[n];
        size=n;
        for(int i=0;i<n;i++){
            data[i]=arr[i];
        }
        Capacity=n;
    }

    Array(){
        data=new T [100];
        this->size=0;
        this->Capacity=100;
    }

    //获得数组的元素个数
    int  getSize(){
        return size;
    }

    //判断数组是否为空
    bool isEmpty(){
        return size==0;
    }

    //获得数组的容量
    int getArray(){
        return Capacity;
    }

    //在数组中插入一个元素
    void add(int index,T elem){
        if(index<0||index>Capacity){
            cout<<"插入的位置有误"<<endl;
            return ;
        }
        if(size>=Capacity){
            resize(Capacity*2);
        }
        for(int i=size-1;i>=index;i--){
            data[i+1]=data[i];
        }
        data[index]=elem;
        size++;
    }

    //在数组的最后一个位置添加一个新元素elem;
    void addLast(T elem){
        add(size,elem);
    }

    //获取index位置的数组元素
    T get(int index){
        if(index<0||index>=size){
            cout<<"您输入的位置有误";
            return -1;
        }
        return data[index];
    }

    //在index位置处修改数组元素的值
    void set(int index,T elem){
        if(index<0||index>=size){
            cout<<"您输入的位置有误";
            return ;
        }
        data[index]=elem;
    }


    //查找数组中是否有元素e
    bool contains(T e){
        for(int i=0;i<size;i++){
            if(data[i]==e)
                return true;
        }
        return false;
    }

    //查找数组中元素e的索引index
    int find(T e){
        for(int i=0;i<size;i++){
            if(data[i]==e)
                return i;
        }
        return -1;
    }

    //删除数组中索引为index位置的元素，并且返回被删除的元素的值
    T remove(int index){
        if(index<0||index>=size){
            return -1;
        }
        T ret=data[index];
        for(int i=index+1;i<size;i++){
            data[i-1]=data[i];
        }
        size--;
        //缩容的时候防止复杂度的震荡
        if(size<Capacity/4&&Capacity/2!=0)
            resize(Capacity/2);
        return ret;
    }

    void swap(int i,int j){
        assert(!(i<0||i>=size||j<0||j>=size));
        T e=data[i];
        data[i]=data[j];
        data[j]=e;
    }

    //改变数组的容量
    void resize(int newCapacity){
        T  *newdata=new T [newCapacity];
        for(int i=0;i<size;i++){
            newdata[i]=data[i];
        }
        data=newdata;
        Capacity=newCapacity;
    }

    //打印数组元素
    void PrintArray(){
        for(int i=0;i<size;i++)
            cout<<data[i]<<" ";
        cout<<endl;
    }
};

######最大堆代码：

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include<iostream>
#include<string>
#include<cassert>
#include<cstdlib>
#include"ArraY.h"
using namespace std;
template<typename E>
class MaxHeap{
private:
    Array <E>*data;

    //从index位置开始向下进行调整操作，保证添加元素后整个数组满足最大堆性质
    void SiftUp(int index){
        assert(index>=0&&index<data->getSize());
        while(index>=0&&data->get(index)>data->get(parent(index))){
                data->swap(index,parent(index));
                index=parent(index);
        }
    }

    //从index位置开始向上进行heapify操作(堆排序中从第一个非叶子节点开始执行该操作)
    void siftDown(int index){
        while(leftChild(index)<data->getSize()){
            int j=leftChild(index);
            if(j+1<data->getSize()&&data->get(j)<data->get(j+1))
                j++;
            if(data->get(j)<=data->get(index))
                break;
            data->swap(j,index);
            index=j;
        }
    }

public:
    MaxHeap(){
        data=new Array<E>();
    }

    //传入一个数组，原地构建最大堆
    MaxHeap(E arr[],int n){
        data=new Array<E>(arr,n);
        int k=parent(data->getSize());
        for(int i=k;i>=0;i--){
            siftDown(i);
        }
    }

    //判断堆是否为空
    bool isEmpty(){
        return data->isEmpty();
    }

    //获得堆中元素的个数
    int getSize(){
        return data->getSize();
    }

    //获得index的父亲节点
    int parent(int index){
        assert(index>=0&&index<=data->getSize());
        return (index-1)/2;
    }

    //获得index的左孩子节点
    int leftChild(int index){
        return 2*index+1;
    }

    //获得index的右孩子节点
    int rightChild(int index){
        return 2*index+2;
    }

    //向堆中添加节点元素e
    void add(E e){
        data->addLast(e);
        SiftUp(data->getSize()-1);
    }

    //返回堆顶的节点元素，并且删除这个节点
    E extractMax(){
        E ret=data->get(0);
        data->swap(0,data->getSize()-1);
        data->remove(data->getSize()-1);
        siftDown(0);
        return ret;
    }

    //获得堆顶的元素，并且把堆顶的元素用元素e替换    
    E replace(E e){
        E ret=data->get(0);
        data->set(0,e);
        siftDown(0);
        return ret;
    }


    //打印堆
    void PrintMaxHeap(){
        for(int i=0;i<data->getSize();i++){
            cout<<data->get(i)<<" ";
        }
        cout<<endl;
    }



};
int main()
{

    int a[]={15,17,19,13,22,16,28,30,41,62};
    MaxHeap <int>*arr=new MaxHeap<int>();
    MaxHeap <int>*arr2=new MaxHeap<int>(a,10);

    arr->add(15);
    arr->add(17);
    arr->add(19);
    arr->add(13);
    arr->add(22);
    arr->add(16);
    arr->add(28);
    arr->add(30);
    arr->add(41);
    arr->add(62);


    cout<<"最大堆:";
    arr->PrintMaxHeap();


    cout<<"最大堆:";
    arr2->PrintMaxHeap();


    return 0;
}

用自己写的动态数组作为底层实现堆，其实这个代码并不是很复杂，只要自己搞懂数组和堆的一些基本特性，然后自己熟悉堆排序，很容易自己Code出来

原文作者：Maple

原文链接：http://yoursite.com/2019/07/10/堆(最大堆)/

发表日期：July 10th 2019, 8:30:11 pm

更新日期：July 10th 2019, 8:30:11 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
Total : 51
2019
Leetcode 算法与数据结构 C++ 洛谷