Skip to content

Latest commit

 

History

History
414 lines (345 loc) · 9.39 KB

从零开始学习数据结构_大堆、小堆.md

File metadata and controls

414 lines (345 loc) · 9.39 KB
Raw

堆排序是十大经典排序算法之一，面试高频知识点，必须懂其原理，能手写代码，下面分析 + 代码值得一看。

一、堆

一种完全二叉树的线性表示方法；就是数组形式保存数据。

  • 大堆：根(父)结点大于左右结点数据 --> 降序；
  • 小堆：根(父)结点小于左右结点数据 --> 升序。

小堆如图：

小堆符合每个根(父)结点都比左右结点小！！！

堆的存储结构，就是一个线性表结构，如下：

private:
    enum{HEAP_DEFAULT_SIZE = 10};  //默认数组空间为10
    Type *heap;     //堆的数组名称
    int capacity;   //堆空间大小
    int size;       //有效元素个数

二、小堆

根据一组无序的数字创建小堆 --> 最后实现堆排！

C++ 中创建小堆，可以通过构造函数一次性创建；也可以调用插入函数创建小堆。

小堆：堆顶的数据最小。

2.1 删除函数

作用：每次删除堆顶，拿最后一个元素放到堆顶，在向下调整成小堆，这样就成升序输出了；

bool remove(Type &v){
    if(size == 0){
        return false;
    }
    v = heap[0];
    heap[0] = heap[size-1];
    size--;
    siftDown(0, size-1);

    return true;
}

2.2 插入函数

作用：向上构建小堆；

bool insert(const Type &x){
    if(size > capacity){
        return false;
    }
    heap[size] = x;
    siftUp(size);
    size++;
    return true;
}

2.3 一次向下调整函数

作用：向下构建小堆

void siftDown(int start, int end){
    int i = start;
    int j = 2*i+1;
    Type tmp = heap[i];

    while(j <= end){
        if(j+1 <= end && heap[j] > heap[j+1]){
            j = j+1;
        }
        if(tmp > heap[j]){
            heap[i] = heap[j];  //要是写交换函数的话，太浪费内存空间！！
        }else{
            break;
        }
        i = j;
        j = 2*i+1;
    }
    heap[i] = tmp;
}

2.4 一次向上调整函数

void siftUp(int start){
    int j = start;
    int i = (j-1)/2;  //父结点,这里的求法要注意。

    Type tmp = heap[j];  //保存的是要插入的数据
    while(j > 0){
        if(heap[i] > tmp){
            heap[j] = heap[i];
        }else{
            break;
        }

        j = i;
        i = (j-1)/2;
    }
    heap[j] = tmp;
}

2.5 小堆完整代码

#ifndef _MIN_HEAP_H_
#define _MIN_HEAP_H_

#include<iostream>
using namespace std;

template<typename Type>
class MinHeap{
public:
    MinHeap(int sz = HEAP_DEFAULT_SIZE){
        capacity = sz > HEAP_DEFAULT_SIZE ? sz : HEAP_DEFAULT_SIZE;
        heap = new Type[capacity];
        size = 0;
    }
    MinHeap(Type ar[], int n){
        capacity = n > HEAP_DEFAULT_SIZE ? n : HEAP_DEFAULT_SIZE;
        heap = new Type[capacity];
        size = n;

        for(int i = 0; i < n; i++){
            heap[i] = ar[i];
        }

        int curPos = n/2 - 1;  //从最后一个非叶子结点开始调整，
        while(curPos >= 0){
            siftDown(curPos, n-1);
            curPos--;  //一直调整到根结点
        }
    }
    ~MinHeap(){
        delete []heap;
        heap = NULL;
        capacity = size = 0;
    }
public:
    bool remove(Type &v){
        if(size == 0){
            return false;
        }
        v = heap[0];
        heap[0] = heap[size-1];
        size--;
        siftDown(0, size-1);

        return true;
    }
    bool insert(const Type &x){
        if(size > capacity){
            return false;
        }
        heap[size] = x;
        siftUp(size);
        size++;
        return true;
    }
    void showHeap()const{
        for(int i = 0; i < size; i++){
            cout<<heap[i]<<" ";
        }
        cout<<endl;
    }
protected:
    void siftDown(int start, int end){
        int i = start;  //父结点
        int j = 2*i+1;  //子节点(左孩子)

        Type tmp = heap[i];
        while(j <= end){
            if(j+1 <= end && heap[j] > heap[j+1]){
                j = j+1;
            }
            if(tmp > heap[j]){
                heap[i] = heap[j];  //要是写交换函数的话，太浪费内存空间！！采用了直接覆盖的方法。
            }else{
                break;
            }
            i = j;
            j = 2*i+1;
        }
        heap[i] = tmp;
    }
    void siftUp(int start){
        int j = start;
        int i = (j-1)/2;  //父结点,这里的求法要注意。

        Type tmp = heap[j];
        while(j > 0){
            if(heap[i] > tmp){
                heap[j] = heap[i];
            }else{
                break;
            }

            j = i;
            i = (j-1)/2;
        }
        heap[j] = tmp;
    }
private:
    enum{HEAP_DEFAULT_SIZE = 10};
    Type *heap;
    int capacity;
    int size;
};

#endif

2.6 测试程序

#include"minHeap.h"

int main(void){
    int ar[] = {53, 17, 78, 9, 45, 65, 87, 23,};
    int n = sizeof(ar)/sizeof(int);
    int i;
    MinHeap<int> hp;
    //MinHeap<int> hp(ar, n);
    for(i = 0; i < n; i++){
        hp.insert(ar[i]);
    }
    hp.showHeap();

    int value;
    for(i = 0; i < n; i++){
        hp.remove(value);
        cout<<value<<" ";
    }
    cout<<endl;
    return 0;
}

2.7 运行结果

三、大堆-->降序

思想和小堆差不多，具体也不再分析了；

3.1 代码如下

#ifndef _MAX_HEAP_H_
#define _MAX_HEAP_H_

#include<iostream>
using namespace std;

template<typename Type>
class MaxHeap{
public:
    MaxHeap(int sz = DEFAULT_HEAP_SIZE){
        capacity = sz > DEFAULT_HEAP_SIZE ? sz : DEFAULT_HEAP_SIZE;
        heap = new Type[capacity];
        size = 0;
    }
    MaxHeap(int ar[], int n){
        capacity = n > DEFAULT_HEAP_SIZE ? n : DEFAULT_HEAP_SIZE;
        heap = new Type[capacity];
        size = n;
        for(int i = 0; i < n; i++){
            heap[i] = ar[i];
        }

        int curPos = n/2-1;
        while(curPos >= 0){
            siftDown(curPos, size-1);
            curPos--;
        }

    }
    ~MaxHeap(){}
public:
    bool insert(const Type &x){
        if(size > capacity){
            return false;    
        }
        heap[size] = x;
        siftUp(size);
        size++;

        return true;
    }
    void remove(int &value){
        value = heap[0];
        heap[0] = heap[size-1];
        size--;
        siftDown(0, size-1);
    }
    void showHeap(){
        for(int i = 0; i < size; i++){
            cout<<heap[i]<<" ";
        }
        cout<<endl;
    }
protected:
    void siftDown(int start, int end){
        int i = start;
        int j = 2*i+1;
        int tmp = heap[i];
        while(j <= end){
            if(j+1 <= end && heap[j] < heap[j+1]){
                j = j+1;
            }

            if(heap[j] > tmp){
                heap[i] = heap[j];
            }else{
                break;
            }
            i = j;
            j = 2*i+1;
        }
        heap[i] = tmp;
    }
    void siftUp(int start){
        int j = start;
        int i = (j-1)/2;
    
        Type tmp = heap[j];
        while(j > 0){
            if(heap[i] < tmp){
                heap[j] = heap[i];
            }else{
                break;
            }
            j = i;
            i = (j-1)/2;
        }
        heap[j] = tmp;
    }
private:
    enum{DEFAULT_HEAP_SIZE = 10};
    Type *heap;
    int capacity;
    int size;
};

#endif

3.2 测试代码

#include"maxHeap.h"

int main(void){
    int ar[] = {23, 45, 12, 6, 4, 9, 33,};
    int n = sizeof(ar)/sizeof(int);
    int i;

    MaxHeap<int> hp;
    for(i = 0; i < n; i++){
        hp.insert(ar[i]);
    }
    hp.showHeap();

    int value;
    for(i = 0; i < n; i++){
        hp.remove(value);
        cout<<value<<" ";
    }
    cout<<endl;
    
    
    return 0;
}

3.3 运行结果

四、说明

原创文章链接：从零开始学习数据结构-->大堆+小堆