堆與堆排序-有解無憂

實作一個堆

實作堆并從堆頂依次取出元素的程序實作了一個簡單的排序

#include <iostream>
#include <algorithm>
#include <string>
#include <ctime>
#include <cmath>
#include <cassert>

using namespace std;


template<typename Item>
class MaxHeap{

private:
    Item *data;
    int count;
    int capacity;

    void shiftUp(int k){
        while( k > 1 && data[k/2] < data[k] ){
            swap( data[k/2], data[k] );
            k /= 2;
        }
    }

    void shiftDown(int k){
        while( 2*k <= count ){
            int j = 2*k; // 在此輪回圈中,data[k]和data[j]交換位置
            if( j+1 <= count && data[j+1] > data[j] )
                j ++;
            // data[j] 是 data[2*k]和data[2*k+1]中的最大值

            if( data[k] >= data[j] ) break;
            swap( data[k] , data[j] );
            k = j;
        }
    }

public:
    // 建構式, 構造一個空堆, 可容納capacity個元素
    MaxHeap(int capacity){
        data = https://www.cnblogs.com/ygjzs/p/new Item[capacity+1];
        count = 0;
        this->capacity = capacity;
    }

    ~MaxHeap(){
        delete[] data;
    }

    // 回傳堆中的元素個數
    int size(){
        return count;
    }

    // 回傳一個布林值, 表示堆中是否為空
    bool isEmpty(){
        return count == 0;
    }

    // 像最大堆中插入一個新的元素 item
    void insert(Item item){
        assert( count + 1 <= capacity );
        data[count+1] = item;
        shiftUp(count+1);
        count ++;
    }

    // 從最大堆中取出堆頂元素, 即堆中所存盤的最大資料
    Item extractMax(){
        assert( count > 0 );
        Item ret = data[1];

        swap( data[1] , data[count] );
        count --;
        shiftDown(1);

        return ret;
    }

    // 獲取最大堆中的堆頂元素
    Item getMax(){
        assert( count > 0 );
        return data[1];
    }

};


// 測驗最大堆
int main() {

    MaxHeap maxheap = MaxHeap(100);

    srand(time(NULL));
    int n = 100;    // 隨機生成n個元素放入最大堆中
    for( int i = 0 ; i < n ; i ++ ){
        maxheap.insert( rand()%100 );
    }

    int* arr = new int[n];
    // 將maxheap中的資料逐漸使用extractMax取出來
    // 取出來的順序應該是按照從大到小的順序取出來的
    for( int i = 0 ; i < n ; i ++ ){
        arr[i] = maxheap.extractMax();
        cout<


一段在控制臺列印樹的代碼
  // 以樹狀列印整個堆結構
    void testPrint(){

        // 我們的testPrint只能列印100個元素以內的堆的樹狀資訊
        if( size() >= 100 ){
            cout<<"This print function can only work for less than 100 int";
            return;
        }

        // 我們的testPrint只能處理整數資訊
        if( typeid(Item) != typeid(int) ){
            cout <<"This print function can only work for int item";
            return;
        }

        cout<<"The max heap size is: "<<size()<<endl;
        cout<<"Data in the max heap: ";
        for( int i = 1 ; i <= size() ; i ++ ){
            // 我們的testPrint要求堆中的所有整數在[0, 100)的范圍內
            assert( data[i] >= 0 && data[i] < 100 );
            cout<<data[i]<<" ";
        }
        cout<<endl;
        cout<<endl;

        int n = size();
        int max_level = 0;
        int number_per_level = 1;
        while( n > 0 ) {
            max_level += 1;
            n -= number_per_level;
            number_per_level *= 2;
        }

        int max_level_number = int(pow(2, max_level-1));
        int cur_tree_max_level_number = max_level_number;
        int index = 1;
        for( int level = 0 ; level < max_level ; level ++ ){
            string line1 = string(max_level_number*3-1, ' ');

            int cur_level_number = min(count-int(pow(2,level))+1,int(pow(2,level)));
            bool isLeft = true;
            for( int index_cur_level = 0 ; index_cur_level < cur_level_number ; index ++ , index_cur_level ++ ){
                putNumberInLine( data[index] , line1 , index_cur_level , cur_tree_max_level_number*3-1 , isLeft );
                isLeft = !isLeft;
            }
            cout<<line1<<endl;

            if( level == max_level - 1 )
                break;

            string line2 = string(max_level_number*3-1, ' ');
            for( int index_cur_level = 0 ; index_cur_level < cur_level_number ; index_cur_level ++ )
                putBranchInLine( line2 , index_cur_level , cur_tree_max_level_number*3-1 );
            cout<<line2<<endl;

            cur_tree_max_level_number /= 2;
        }
    }

private:
    void putNumberInLine( int num, string &line, int index_cur_level, int cur_tree_width, bool isLeft){

        int sub_tree_width = (cur_tree_width - 1) / 2;
        int offset = index_cur_level * (cur_tree_width+1) + sub_tree_width;
        assert(offset + 1 < line.size());
        if( num >= 10 ) {
            line[offset + 0] = '0' + num / 10;
            line[offset + 1] = '0' + num % 10;
        }
        else{
            if( isLeft)
                line[offset + 0] = '0' + num;
            else
                line[offset + 1] = '0' + num;
        }
    }

    void putBranchInLine( string &line, int index_cur_level, int cur_tree_width){

        int sub_tree_width = (cur_tree_width - 1) / 2;
        int sub_sub_tree_width = (sub_tree_width - 1) / 2;
        int offset_left = index_cur_level * (cur_tree_width+1) + sub_sub_tree_width;
        assert( offset_left + 1 < line.size() );
        int offset_right = index_cur_level * (cur_tree_width+1) + sub_tree_width + 1 + sub_sub_tree_width;
        assert( offset_right < line.size() );

        line[offset_left + 1] = '/';
        line[offset_right + 0] = '\\';
    }

堆排序
一種是上面已經實作的排序
template<typename T>
void heapSort1(T arr[], int n){

    MaxHeap<T> maxheap = MaxHeap<T>(n);
    for( int i = 0 ; i < n ; i ++ )
        maxheap.insert(arr[i]);

    for( int i = n-1 ; i >= 0 ; i-- )
        arr[i] = maxheap.extractMax();

}

heapSort1, 將所有的元素依次添加到堆中, 在將所有元素從堆中依次取出來, 即完成了排序,無論是創建堆的程序, 還是從堆中依次取出元素的程序, 時間復雜度均為O(nlogn),整個堆排序的整體時間復雜度為O(nlogn)
對其進行優化
// 建構式, 通過一個給定陣列創建一個最大堆
    // 該構造堆的程序, 時間復雜度為O(n)
    MaxHeap(Item arr[], int n){
        data = https://www.cnblogs.com/ygjzs/p/new Item[n+1];
        capacity = n;

        for( int i = 0 ; i < n ; i ++ )
            data[i+1] = arr[i];
        count = n;

        for( int i = count/2 ; i >= 1 ; i -- )
            shiftDown(i);
    }

template<typename T>
void heapSort2(T arr[], int n){

    MaxHeap<T> maxheap = MaxHeap<T>(arr,n);
    for( int i = n-1 ; i >= 0 ; i-- )
        arr[i] = maxheap.extractMax();

}

heapSort2, 借助我們的heapify程序創建堆,此時, 創建堆的程序時間復雜度為O(n), 將所有元素依次從堆中取出來, 實踐復雜度為O(nlogn),堆排序的總體時間復雜度依然是O(nlogn), 但是比上述heapSort1性能更優, 因為創建堆的性能更優
原地堆排序
// 不使用一個額外的最大堆, 直接在原陣列上進行原地的堆排序
template<typename T>
void heapSort(T arr[], int n){

    // 注意，此時的堆是從0開始索引的
    // 從(最后一個元素的索引-1)/2開始
    // 最后一個元素的索引 = n-1
    for( int i = (n-1-1)/2 ; i >= 0 ; i -- )
        __shiftDown2(arr, n, i);

    for( int i = n-1; i > 0 ; i-- ){
        swap( arr[0] , arr[i] );
        __shiftDown2(arr, i, 0);
    }
}

// 優化的shiftDown程序, 使用賦值的方式取代不斷的swap,
// 該優化思想和我們之前對插入排序進行優化的思路是一致的
template<typename T>
void __shiftDown2(T arr[], int n, int k){

    T e = arr[k];
    while( 2*k+1 < n ){
        int j = 2*k+1;
        if( j+1 < n && arr[j+1] > arr[j] )
            j += 1;

        if( e >= arr[j] ) break;

        arr[k] = arr[j];
        k = j;
    }

    arr[k] = e;
}

索引堆
#include <iostream>
#include <cassert>
#include "SortTestHelper.h"

using namespace std;

// 最大索引堆
template<typename Item>
class IndexMaxHeap{

private:
    Item *data;     // 最大索引堆中的資料
    int *indexes;   // 最大索引堆中的索引

    int count;
    int capacity;

    // 索引堆中, 資料之間的比較根據data的大小進行比較, 但實際操作的是索引
    void shiftUp( int k ){

        while( k > 1 && data[indexes[k/2]] < data[indexes[k]] ){
            swap( indexes[k/2] , indexes[k] );
            k /= 2;
        }
    }

    // 索引堆中, 資料之間的比較根據data的大小進行比較, 但實際操作的是索引
    void shiftDown( int k ){

        while( 2*k <= count ){
            int j = 2*k;
            if( j + 1 <= count && data[indexes[j+1]] > data[indexes[j]] )
                j += 1;

            if( data[indexes[k]] >= data[indexes[j]] )
                break;

            swap( indexes[k] , indexes[j] );
            k = j;
        }
    }

public:
    // 建構式, 構造一個空的索引堆, 可容納capacity個元素
    IndexMaxHeap(int capacity){

        data = https://www.cnblogs.com/ygjzs/p/new Item[capacity+1];
        indexes = new int[capacity+1];

        count = 0;
        this->capacity = capacity;
    }

    ~IndexMaxHeap(){
        delete[] data;
        delete[] indexes;
    }

    // 回傳索引堆中的元素個數
    int size(){
        return count;
    }

    // 回傳一個布林值, 表示索引堆中是否為空
    bool isEmpty(){
        return count == 0;
    }

    // 向最大索引堆中插入一個新的元素, 新元素的索引為i, 元素為item
    // 傳入的i對用戶而言,是從0索引的
    void insert(int i, Item item){
        assert( count + 1 <= capacity );
        assert( i + 1 >= 1 && i + 1 <= capacity );

        i += 1;
        data[i] = item;
        indexes[count+1] = i;
        count++;

        shiftUp(count);
    }

    // 從最大索引堆中取出堆頂元素, 即索引堆中所存盤的最大資料
    Item extractMax(){
        assert( count > 0 );

        Item ret = data[indexes[1]];
        swap( indexes[1] , indexes[count] );
        count--;
        shiftDown(1);
        return ret;
    }

    // 從最大索引堆中取出堆頂元素的索引
    int extractMaxIndex(){
        assert( count > 0 );

        int ret = indexes[1] - 1;
        swap( indexes[1] , indexes[count] );
        count--;
        shiftDown(1);
        return ret;
    }

    // 獲取最大索引堆中的堆頂元素
    Item getMax(){
        assert( count > 0 );
        return data[indexes[1]];
    }

    // 獲取最大索引堆中的堆頂元素的索引
    int getMaxIndex(){
        assert( count > 0 );
        return indexes[1]-1;
    }

    // 獲取最大索引堆中索引為i的元素
    Item getItem( int i ){
        assert( i + 1 >= 1 && i + 1 <= capacity );
        return data[i+1];
    }

    // 將最大索引堆中索引為i的元素修改為newItem
    void change( int i , Item newItem ){

        i += 1;
        data[i] = newItem;

        // 找到indexes[j] = i, j表示data[i]在堆中的位置
        // 之后shiftUp(j), 再shiftDown(j)
        for( int j = 1 ; j <= count ; j ++ )
            if( indexes[j] == i ){
                shiftUp(j);
                shiftDown(j);
                return;
            }
    }

    // 測驗索引堆中的索引陣列index
    // 注意:這個測驗在向堆中插入元素以后, 不進行extract操作有效
    bool testIndexes(){

        int *copyIndexes = new int[count+1];

        for( int i = 0 ; i <= count ; i ++ )
            copyIndexes[i] = indexes[i];

        copyIndexes[0] = 0;
        std::sort(copyIndexes, copyIndexes + count + 1);

        // 在對索引堆中的索引進行排序后, 應該正好是1...count這count個索引
        bool res = true;
        for( int i = 1 ; i <= count ; i ++ )
            if( copyIndexes[i-1] + 1 != copyIndexes[i] ){
                res = false;
                break;
            }

        delete[] copyIndexes;

        if( !res ){
            cout<<"Error!"<<endl;
            return false;
        }

        return true;
    }
};

反向查找表
#include <iostream>
#include <cassert>
#include "SortTestHelper.h"

using namespace std;

// 最大索引堆
template<typename Item>
class IndexMaxHeap{

private:
    Item *data;     // 最大索引堆中的資料
    int *indexes;   // 最大索引堆中的索引, indexes[x] = i 表示索引i在x的位置
    int *reverse;   // 最大索引堆中的反向索引, reverse[i] = x 表示索引i在x的位置

    int count;
    int capacity;

    // 索引堆中, 資料之間的比較根據data的大小進行比較, 但實際操作的是索引
    void shiftUp( int k ){

        while( k > 1 && data[indexes[k/2]] < data[indexes[k]] ){
            swap( indexes[k/2] , indexes[k] );
            reverse[indexes[k/2]] = k/2;
            reverse[indexes[k]] = k;
            k /= 2;
        }
    }

    // 索引堆中, 資料之間的比較根據data的大小進行比較, 但實際操作的是索引
    void shiftDown( int k ){

        while( 2*k <= count ){
            int j = 2*k;
            if( j + 1 <= count && data[indexes[j+1]] > data[indexes[j]] )
                j += 1;

            if( data[indexes[k]] >= data[indexes[j]] )
                break;

            swap( indexes[k] , indexes[j] );
            reverse[indexes[k]] = k;
            reverse[indexes[j]] = j;
            k = j;
        }
    }

public:
    // 建構式, 構造一個空的索引堆, 可容納capacity個元素
    IndexMaxHeap(int capacity){

        data = https://www.cnblogs.com/ygjzs/p/new Item[capacity+1];
        indexes = new int[capacity+1];
        reverse = new int[capacity+1];
        for( int i = 0 ; i <= capacity ; i ++ )
            reverse[i] = 0;

        count = 0;
        this->capacity = capacity;
    }

    ~IndexMaxHeap(){
        delete[] data;
        delete[] indexes;
        delete[] reverse;
    }

    // 回傳索引堆中的元素個數
    int size(){
        return count;
    }

    // 回傳一個布林值, 表示索引堆中是否為空
    bool isEmpty(){
        return count == 0;
    }

    // 向最大索引堆中插入一個新的元素, 新元素的索引為i, 元素為item
    // 傳入的i對用戶而言,是從0索引的
    void insert(int i, Item item){
        assert( count + 1 <= capacity );
        assert( i + 1 >= 1 && i + 1 <= capacity );

        // 再插入一個新元素前,還需要保證索引i所在的位置是沒有元素的，
        assert( !contain(i) );

        i += 1;
        data[i] = item;
        indexes[count+1] = i;
        reverse[i] = count+1;
        count++;

        shiftUp(count);
    }

    // 從最大索引堆中取出堆頂元素, 即索引堆中所存盤的最大資料
    Item extractMax(){
        assert( count > 0 );

        Item ret = data[indexes[1]];
        swap( indexes[1] , indexes[count] );
        reverse[indexes[count]] = 0;
        count--;

        if(count){
            reverse[indexes[1]] = 1;
            shiftDown(1);
        }

        return ret;
    }

    // 從最大索引堆中取出堆頂元素的索引
    int extractMaxIndex(){
        assert( count > 0 );

        int ret = indexes[1] - 1;
        swap( indexes[1] , indexes[count] );
        reverse[indexes[count]] = 0;
        count--;

        if(count) {
            reverse[indexes[1]] = 1;
            shiftDown(1);
        }

        return ret;
    }

    // 獲取最大索引堆中的堆頂元素
    Item getMax(){
        assert( count > 0 );
        return data[indexes[1]];
    }

    // 獲取最大索引堆中的堆頂元素的索引
    int getMaxIndex(){
        assert( count > 0 );
        return indexes[1]-1;
    }

    // 看索引i所在的位置是否存在元素
    bool contain( int i ){
        assert( i + 1 >= 1 && i + 1 <= capacity );
        return reverse[i+1] != 0;
    }

    // 獲取最大索引堆中索引為i的元素
    Item getItem( int i ){
        assert( contain(i) );
        return data[i+1];
    }

    // 將最大索引堆中索引為i的元素修改為newItem
    void change( int i , Item newItem ){

        assert( contain(i) );
        i += 1;
        data[i] = newItem;

        // 有了 reverse 之后,
        // 我們可以非常簡單的通過reverse直接定位索引i在indexes中的位置
        shiftUp( reverse[i] );
        shiftDown( reverse[i] );
    }

    // 測驗索引堆中的索引陣列index和反向陣列reverse
    // 注意:這個測驗在向堆中插入元素以后, 不進行extract操作有效
    bool testIndexesAndReverseIndexes(){

        int *copyIndexes = new int[count+1];
        int *copyReverseIndexes = new int[count+1];

        for( int i = 0 ; i <= count ; i ++ ){
            copyIndexes[i] = indexes[i];
            copyReverseIndexes[i] = reverse[i];
        }

        copyIndexes[0] = copyReverseIndexes[0] = 0;
        std::sort(copyIndexes, copyIndexes + count + 1);
        std::sort(copyReverseIndexes, copyReverseIndexes + count + 1);

        // 在對索引堆中的索引和反向索引進行排序后,
        // 兩個陣列都應該正好是1...count這count個索引
        bool res = true;
        for( int i = 1 ; i <= count ; i ++ )
            if( copyIndexes[i-1] + 1 != copyIndexes[i] ||
                    copyReverseIndexes[i-1] + 1 != copyReverseIndexes[i] ){
                res = false;
                break;
            }

        delete[] copyIndexes;
        delete[] copyReverseIndexes;

        if( !res ){
            cout<<"Error!"<<endl;
            return false;
        }

        for( int i = 1 ; i <= count ; i ++ )
            if( reverse[ indexes[i] ] != i ){
                cout<<"Error 2"<<endl;
                return false;
            }

        return true;
    }
};

最小堆
#include <algorithm>
#include <cassert>

using namespace std;

// 最小堆
template<typename Item>
class MinHeap{

private:
    Item *data;
    int count;
    int capacity;

    void shiftUp(int k){
        while( k > 1 && data[k/2] > data[k] ){
            swap( data[k/2], data[k] );
            k /= 2;
        }
    }

    void shiftDown(int k){
        while( 2*k <= count ){
            int j = 2*k;
            if( j+1 <= count && data[j+1] < data[j] ) j ++;
            if( data[k] <= data[j] ) break;
            swap( data[k] , data[j] );
            k = j;
        }
    }

public:

    // 建構式, 構造一個空堆, 可容納capacity個元素
    MinHeap(int capacity){
        data = https://www.cnblogs.com/ygjzs/p/new Item[capacity+1];
        count = 0;
        this->capacity = capacity;
    }

    // 建構式, 通過一個給定陣列創建一個最小堆
    // 該構造堆的程序, 時間復雜度為O(n)
    MinHeap(Item arr[], int n){
        data = new Item[n+1];
        capacity = n;

        for( int i = 0 ; i < n ; i ++ )
            data[i+1] = arr[i];
        count = n;

        for( int i = count/2 ; i >= 1 ; i -- )
            shiftDown(i);
    }

    ~MinHeap(){
        delete[] data;
    }

    // 回傳堆中的元素個數
    int size(){
        return count;
    }

    // 回傳一個布林值, 表示堆中是否為空
    bool isEmpty(){
        return count == 0;
    }

    // 向最小堆中插入一個新的元素 item
    void insert(Item item){
        assert( count + 1 <= capacity );
        data[count+1] = item;
        shiftUp(count+1);
        count ++;
    }

    // 從最小堆中取出堆頂元素, 即堆中所存盤的最小資料
    Item extractMin(){
        assert( count > 0 );
        Item ret = data[1];
        swap( data[1] , data[count] );
        count --;
        shiftDown(1);
        return ret;
    }

    // 獲取最小堆中的堆頂元素
    Item getMin(){
        assert( count > 0 );
        return data[1];
    }
};

索引最小堆
#include <iostream>
#include <algorithm>
#include <cassert>

using namespace std;

// 最小索引堆
template<typename Item>
class IndexMinHeap{

private:
    Item *data;     // 最小索引堆中的資料
    int *indexes;   // 最小索引堆中的索引, indexes[x] = i 表示索引i在x的位置
    int *reverse;   // 最小索引堆中的反向索引, reverse[i] = x 表示索引i在x的位置

    int count;
    int capacity;

    // 索引堆中, 資料之間的比較根據data的大小進行比較, 但實際操作的是索引
    void shiftUp( int k ){

        while( k > 1 && data[indexes[k/2]] > data[indexes[k]] ){
            swap( indexes[k/2] , indexes[k] );
            reverse[indexes[k/2]] = k/2;
            reverse[indexes[k]] = k;
            k /= 2;
        }
    }

    // 索引堆中, 資料之間的比較根據data的大小進行比較, 但實際操作的是索引
    void shiftDown( int k ){

        while( 2*k <= count ){
            int j = 2*k;
            if( j + 1 <= count && data[indexes[j]] > data[indexes[j+1]] )
                j += 1;

            if( data[indexes[k]] <= data[indexes[j]] )
                break;

            swap( indexes[k] , indexes[j] );
            reverse[indexes[k]] = k;
            reverse[indexes[j]] = j;
            k = j;
        }
    }

public:
    // 建構式, 構造一個空的索引堆, 可容納capacity個元素
    IndexMinHeap(int capacity){

        data = https://www.cnblogs.com/ygjzs/p/new Item[capacity+1];
        indexes = new int[capacity+1];
        reverse = new int[capacity+1];

        for( int i = 0 ; i <= capacity ; i ++ )
            reverse[i] = 0;

        count = 0;
        this->capacity = capacity;
    }

    ~IndexMinHeap(){
        delete[] data;
        delete[] indexes;
        delete[] reverse;
    }

    // 回傳索引堆中的元素個數
    int size(){
        return count;
    }

    // 回傳一個布林值, 表示索引堆中是否為空
    bool isEmpty(){
        return count == 0;
    }

    // 向最小索引堆中插入一個新的元素, 新元素的索引為i, 元素為item
    // 傳入的i對用戶而言,是從0索引的
    void insert(int index, Item item){
        assert( count + 1 <= capacity );
        assert( index + 1 >= 1 && index + 1 <= capacity );

        index += 1;
        data[index] = item;
        indexes[count+1] = index;
        reverse[index] = count+1;
        count++;
        shiftUp(count);
    }

    // 從最小索引堆中取出堆頂元素, 即索引堆中所存盤的最小資料
    Item extractMin(){
        assert( count > 0 );

        Item ret = data[indexes[1]];
        swap( indexes[1] , indexes[count] );
        reverse[indexes[count]] = 0;
        count--;

        if(count){
            reverse[indexes[1]] = 1;
            shiftDown(1);
        }

        return ret;
    }

    // 從最小索引堆中取出堆頂元素的索引
    int extractMinIndex(){
        assert( count > 0 );

        int ret = indexes[1] - 1;
        swap( indexes[1] , indexes[count] );
        reverse[indexes[count]] = 0;
        count--;

        if(count){
            reverse[indexes[1]] = 1;
            shiftDown(1);
        }

        return ret;
    }

    // 獲取最小索引堆中的堆頂元素
    Item getMin(){
        assert( count > 0 );
        return data[indexes[1]];
    }

    // 獲取最小索引堆中的堆頂元素的索引
    int getMinIndex(){
        assert( count > 0 );
        return indexes[1]-1;
    }

    // 看索引i所在的位置是否存在元素
    bool contain( int index ){

        return reverse[index+1] != 0;
    }

    // 獲取最小索引堆中索引為i的元素
    Item getItem( int index ){
        assert( contain(index) );
        return data[index+1];
    }

    // 將最小索引堆中索引為i的元素修改為newItem
    void change( int index , Item newItem ){

        assert( contain(index) );
        index += 1;
        data[index] = newItem;

        shiftUp( reverse[index] );
        shiftDown( reverse[index] );
    }

};






        
      轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/199356.html
      標籤：其他 
      上一篇：N皇后問題 回溯遞回演算法 C++實作1
下一篇：資料結構（C語言版）---線性表