0.x 11.堆和堆排序

dddd数据结构课本

• Author：李英民 | Henry
• E-mail: li_yingmin@outlookdotcom
• $Beijing~~U~of~Posts~and~Telecom$$(BUPT~)$
• Home: https://liyingmin.wixsite.com/henry

• 快速了解我: About Me

• 转载请保留上述引用内容，谢谢配合！

shiftUp逐渐插入元素+堆输出

#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>
#include <typeinfo>
#include <numeric>
#include <memory>
#include <stdexcept>
#include <fstream> 
#include <cmath>
#include <ctime>
#include <utility>
#include <sstream>
#include <random>
#include <cassert>
using namespace std;
//win+<-/-> 切换窗口位置
//ctrl+win+<-/->切换桌面 
//ctrl+alt+上/下 改变显示器方向 
template<typename Item>
class MaxHeap{
private:
    Item *data;
    int count;
    void shiftUp(int k)
    {
        while(k/2 >= 1)
        {
            if(data[k/2]>=data[k]) break;
            swap(data[k/2], data[k]);
            k /= 2;
        }
    }
    void shiftDown(int k)
    {
        while(2*k <= count)
        {
            int j = 2*k;
            if(2*k + 1<=count && data[j+1] > data[j])
                j += 1;
            if(data[k] >= data[j])
                break;
            swap(data[k], data[j]);
            k = j;
        }
    }
public:
    // 构造函数, 构造一个空堆, 可容纳capacity个元素
    MaxHeap(int capacity):data(new Item[capacity+1]{}),count(0) {}
    ~MaxHeap(){
        delete[] data;
    }
    // 返回堆中的元素个数
    int size(){
        return count;
    }
    // 返回一个布尔值, 表示堆中是否为空
    bool isEmpty(){
        return count == 0;
    }
    void insert(Item item)  //插入并shiftUp
    {
        data[++count] = item;
        shiftUp(count); 
    } 
    Item extractMax()  //输出根结点，并将最后一个挪到data[1]，然后shiftDown
    {
        Item ret = data[1];
        data[1] = data[count--];
        shiftDown(1);
        return ret;
    }
};
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();
}
int main() {
    int a[40]{1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10};
    heapSort1(a,40);
    for(auto x:a)
        cout<<x<<ends;
    cout<<endl;
    return 0;
}

Heapify+shiftDown+输出根结点

#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>
#include <typeinfo>
#include <numeric>
#include <memory>
#include <stdexcept>
#include <fstream> 
#include <cmath>
#include <ctime>
#include <utility>
#include <sstream>
#include <random>
#include <cassert>
using namespace std;
//win+<-/-> 切换窗口位置
//ctrl+win+<-/->切换桌面 
//ctrl+alt+上/下 改变显示器方向 
template<typename Item>
class MaxHeap{
private:
    Item *data;
    int count;
    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(2*k + 1<=count && data[j+1] > data[j])
                j += 1;
            if(data[k] >= data[j])
                break;
            else swap(data[k], data[j]);
            k = j;
        }
    }
public:
    // 构造函数, 构造一个空堆, 可容纳capacity个元素
    MaxHeap(int capacity):data(new Item[capacity+1]{}),count(0) {}
    MaxHeap(Item arr[], int n ):data(new Item[n+1]{}),count(n)
    {
        for(int i = 0; i != n; ++i)
            data[i+1] = arr[i];
        int k = n/2;
        while(k >= 1)
        {
            shiftDown(k--);
        }
    }
    ~MaxHeap(){
        delete[] data;
    }
    // 返回堆中的元素个数
    int size(){
        return count;
    }
    // 返回一个布尔值, 表示堆中是否为空
    bool isEmpty(){
        return count == 0;
    }
    void insert(Item item)
    {
        data[++count] = item;
        shiftUp(count); 
    } 
    Item extractMax()
    {
        Item ret = data[1];
        data[1] = data[count--];
        shiftDown(1);
        return ret;
    }
};
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();
}
int main() {
    int a[40]{1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10};
    heapSort2(a,40);
    for(auto x:a)
        cout<<x<<ends;
    cout<<endl;
    return 0;
}

原地堆排序

#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>
#include <typeinfo>
#include <numeric>
#include <memory>
#include <stdexcept>
#include <fstream> 
#include <cmath>
#include <ctime>
#include <utility>
#include <sstream>
#include <random>
#include <cassert>
using namespace std;
//win+<-/-> 切换窗口位置
//ctrl+win+<-/->切换桌面 
//ctrl+alt+上/下 改变显示器方向
// 原始的shiftDown过程
template<typename T>
void __shiftDown(T arr[], int n, int k){
    while( 2*k+1 < n ){
        int j = 2*k+1;
        if( j+1 < n && arr[j+1] > arr[j] )
            j += 1;
        if( arr[k] >= arr[j] )break;
        swap( arr[k] , arr[j] );
        k = j;
    }
}
// 优化的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;
}
// 不使用一个额外的最大堆, 直接在原数组上进行原地的堆排序
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);
    }
}
int main() {
    int a[40]{1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10};
    heapSort(a,40);
    for(auto x:a)
        cout<<x<<ends;
    cout<<endl;
    return 0;
}