算法与数据结构（四）堆排序：优先队列实现

堆排序

排序次要的，接触新的数据结构；堆

堆和优先队列 Heap and Priority Queue

什么是优先队列？

• 普通队列：先进先出；后进后出

• 优先队列：出队顺序和入队顺序无关；和优先级相关

为什么使用优先队列。操作系统将cpu的时间划成时间片。每个时间片只执行一个：使用优先队列动态选择优先级最高的任务执行。

动态选择

关键词：动态

cpu

不能一次性排序。因为变化多。媒体服务接受响应，处理的顺序使用优先队列。

游戏中决定选择优先攻击哪个敌人：最近 & 血最少

优先攻击

敌人动态的消灭，动态的增加。

在1,000,000个元素中选出前100名？

在N个元素中选出前M个元素

排序? nlogn
使用优先队列 nlogm

优先队列的主要操作：

• 入队
• 出队（取出优先级最高的元素）

实现：

三种实现

使用堆可以平衡入队和出队。

对于总共N个请求：
使用普通数组或者顺序数组，最差情况：O(n^2)
使用堆稳定在：O(nlgn)

堆的基本实现

二叉堆 Binary Heap

• 像一个二叉树

二叉堆

每一个节点可以有两个子节点。

特点：

• 任何一个子节点都不大于父节点
• 二叉堆是一颗完全二叉树

堆中某个节点的值总是不大于其父节点的值；
堆总是一棵完全二叉树。（最大堆）

完全二叉树

完全二叉树：除最后一层节点外，其它层节点个数必须是最大值。
最后一层所有节点必须集中在左侧。

最大堆。树顶的元素总是最大值。
最小堆。树顶的元素总是最小值。

父节点的值大于子节点的值:不意味着层数越高数值越大。

节点有左右两个指针指向左孩子，右孩子。用数组存储二叉堆。
因为堆是一颗完全二叉树。

数组存储二叉堆

左节点值为自身的2倍。而右节点为自身的2倍+1

根节点标为0.左右更好。
通常使用从1开始的下标：

从1开始的数组 父子节点的计算公式

父节点的计算公式为整数式，整数取整。

空最大堆代码：

#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;

public:
    //数组初始化，开辟空间
    MaxHeap(int capacity){
        //从索引1开始
        data = new Item[capacity+1];
        count = 0;
    }

    ~MaxHeap(){
        delete[] data;
    }
    
    int size(){
        return count;
    }

    bool isEmpty(){
        return count == 0;
    }
};


int main() {

    MaxHeap<int> maxheap = MaxHeap<int>(100);
    cout<<maxheap.size()<<endl;

    return 0;
}

运行结果：0

如何向最大堆中添加元素。

Shift up

shift - up

此时插入52大于父节点16违背了堆的定义。

子节点与父节点交换一次位置。

父子节点交换位置 父子节点再次交换位置

#include <iostream>
#include <algorithm>
#include <string>
#include <ctime>
#include <cmath>
#include <cassert>
#include <typeinfo>
using namespace std;


template<typename Item>
class MaxHeap{

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

    //将位置k的元素尝试向上移动
    void shiftUp(int k){
        while( k > 1 && data[k/2] < data[k] ){
            swap( data[k/2], data[k] );
            //交换过之后考虑当前节点，就是上次节点交换后的位置
            k /= 2;
        }
    }

public:

    MaxHeap(int capacity){
        data = new Item[capacity+1];
        count = 0;
        this->capacity = capacity;
    }

    ~MaxHeap(){
        delete[] data;
    }

    int size(){
        return count;
    }

    bool isEmpty(){
        return count == 0;
    }

    void insert(Item item){
        assert( count + 1 <= capacity );
        data[count+1] = item;
        count ++;
        //通过shiftup保持堆的定义
        shiftUp(count);
    }


public:
    void testPrint(){

        if( size() >= 100 ){
            cout<<"Fancy print can only work for less than 100 int";
            return;
        }

        if( typeid(Item) != typeid(int) ){
            cout <<"Fancy print can only work for int item";
            return;
        }

        cout<<"The Heap size is: "<<size()<<endl;
        cout<<"data in heap: ";
        for( int i = 1 ; i <= size() ; i ++ )
            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] = '\\';
    }
};


int main() {

    MaxHeap<int> maxheap = MaxHeap<int>(100);

    srand(time(NULL));
    for( int i = 0 ; i < 50 ; i ++ ){
        maxheap.insert( rand()%100 );
    }
    maxheap.testPrint();

    return 0;
}

重点方法：shiftup和inserted

shfit Down从堆中取出一个元素。

从堆中取元素，只能取出根节点的元素。如何填补这个元素？

把堆中最后一个元素放到根节点。

count --

比较两个子节点，谁大跟谁换。

 Item extractMax(){
        assert( count > 0 );
        Item ret = data[1];

        //最后一个元素和第一个元素进行互换
        swap( data[1] , data[count] );
        count --;
        shiftDown(1);

        return ret;
    }


    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更新为j+1
                j ++;
            // data[j] 是 data[2*k]和data[2*k+1]中的最大值

            if( data[k] >= data[j] ) break;
            swap( data[k] , data[j] );
            //新的变到了j的位置
            k = j;
        }
    }  


int main() {

    MaxHeap<int> maxheap = MaxHeap<int>(100);

    srand(time(NULL));
    for( int i = 0 ; i < 63 ; i ++ ){
        maxheap.insert( rand()%100 );
    }

    while( !maxheap.isEmpty() )
        //取出最大值的同时也删除了.
        cout<<maxheap.extractMax()<<" ";
    cout<<endl;

    return 0;
}

可选的优化：

将swap操作变为直到找到它的合适位置然后赋值。

运行结果

堆排序nlogn级别的

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-- )
        //从大的i存大的值。小的i存小值。形成一个正序
        arr[i] = maxheap.extractMax();

}

把数组插入堆中，然后再extract出来。

heapify

五个叶子节点，可以看出五个最大堆
最后一个非叶子节点的值是元素个数/2（从索引1开始计算）

heapify

对于非叶节点执行shiftDown。

 MaxHeap(Item arr[], int n){
        data = new Item[n+1];
        capacity = n;

        for( int i = 0 ; i < n ; i ++ )
            //下标从1开始
            data[i+1] = arr[i];
        count = n;

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

    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();

}

构建堆的不同方法的运行结果差异

我们优化过的堆排序还是不如归并排序和快速排序的，但是比直接插入的快了。

堆适合动态数据的维护。不是很适合排序。

将n个元素逐个插入到一个空堆中，算法复杂度是O(nlogn)
heapify的过程，算法复杂度为O(n)

上面的方法中都对于数组内容整个放入堆中。下面我们改造成一个原地改造。

原地堆排序

MaxHeap。

最大值

排好的最大堆数组第一个元素是最大值。那么将它与最后一个元素互换。最后一个元素为最大值。

对w进行一次shiftdown操作，将橙色部分转变为最大堆。

shift-Down

注意：heapify & shiftDown因为直接在数组上进行的，所以应该从0开始。

从0开始的父子节点公式 heapify中最后一个非叶子节点的索引

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;
    }
}

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){

    //heapify操作，第一个非叶子节点和终止条件
    for( int i = (n-1)/2 ; i >= 0 ; i -- )
//        因为不在类里访问不到成员变量。对第i个索引进行。
        __shiftDown2(arr, n, i);

    for( int i = n-1; i > 0 ; i-- ){
        //把当前0号位置的元素放到它合适的位置
        swap( arr[0] , arr[i] );
        //有i个元素，对于0号索引进行shiftDown
        __shiftDown2(arr, i, 0);
    }
}

shiftDown2是选取到合适位置直接赋值快于一直交换。
因为原地堆排序不需要开辟新的内存空间。快一点。

排序算法总结

排序算法对比

平均时间复杂度。

• 对于插入排序如果要排序的数组已经是有序的，O(n)
• 对于快速排序，它可以退化到O(n^2)级别。(随机化处理使得这一情况可能性极低)
• 快排是更加快的一种。常数级别低。对于有可能有大量重复键值的我们可以使用三路快速排序。

原地排序：在数组上直接交换元素。

因为插入排序和堆排序可以直接在数组上交换元素来完成。所以是O(1)级别的。

• 快速排序采用递归方式进行，有logn层递归，这么多层递归就导致有相应的logn层栈空间来保存每一次递归的空间。

排序算法的稳定性：

稳定排序：对于相等的元素，在排序后，原来靠前的元素依然靠前。
相等元素的相对位置没有发生改变。

初始数组:红绿蓝。排序后依然红绿蓝

稳定排序可以做到排序成绩之后，相同成绩仍然是按照学号顺序的。

稳定排序1：插入排序

插入排序3的位置

3比8小交换位置，3比6小交换位置。3和3等不动。

稳定排序2：归并排序

归并排序

归并过程中1比2小，1上。2比3小，2上。三和三。前面的3先上。

归并排序中当n小的时候，使用插入排序做优化，仍然使得归并有序。
与具体实现相关。

快速排序：标准点随机选择。
数组组建成堆破坏顺序。

可以通过自定义比较函数，让排序算法不存在稳定性的问题。

bool operator<(const Student& otherStudent){
        
    return score != otherStudent.score ?
               score > otherStudent.score : 
          name < otherStudent.name;
}

系统级的稳定排序大多选择归并。

神秘的最优算法

索引堆（Index Heap）

数组构建成堆

构建前构建后，数组元素的位置发生了改变。

• 元素是复杂元素。交换消耗巨大。
• 元素在数组中位置发生了改变。堆建成后很难索引到元素。

例如:可能数组初始的时候索引表示的是它的进程号。值为优先级。
构建为堆后数组索引和进程号不关联了。想把某个进程优先级提一提就很难了

索引堆。

索引堆中数据和索引分开 构建成堆之后

也就是数组的索引仍然是原来data的索引值。

而新增的index是构建成堆之后的数组索引。

如果想把进程号为7的提一提优先级。很简单的把7的data28改为38。
维持堆的性质，根据新的data，改变index。

创建索引堆。元素比较比较data。真正元素交换交换index。

private:
    Item *data;
    int *indexes;

    int count;
    int capacity;

 IndexMaxHeap(int capacity){

        data = new Item[capacity+1];
        indexes = new int[capacity+1];

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

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

    // 传入的i对用户而言,是从0索引的
    void insert(int i, Item item){
        assert( count + 1 <= capacity );
        assert( i + 1 >= 1 && i + 1 <= capacity );

        i += 1;
        data[i] = item;
//        index末尾添加新的索引i
        indexes[count+1] = i;
        count++;

        shiftUp(count);
    }

       void shiftUp( int k ){
    //找到k位置的index-》找data
        while( k > 1 && data[indexes[k/2]] < data[indexes[k]] ){
            swap( indexes[k/2] , indexes[k] );
            k /= 2;
        }
    }

      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;
        }
    }


  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;
    }

    Item getItem( int i ){
        return data[i+1];
    }

     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;
            }
    }

change因为进行了遍历寻找，时间复杂度达到了O(n)级别。
我们要对这个进行一定的优化。

优化更改元素。拥有reverse反向查找的Index Max Heap

经典的提速思路（反向查找）

反向数组 index max heap

如：revese[i] 表示索引i在indexes（堆）中的位置

reverse[4] = 9;就表示4这个索引，在index中的位置为9.

同时根据index维护reverse。

private:
    Item *data;
    int *indexes;
    int *reverse;

    int count;
    int capacity;

public:
    IndexMaxHeap(int capacity){

        data = new Item[capacity+1];
        indexes = new int[capacity+1];
        reverse = new int[capacity+1];
        for( int i = 0 ; i <= capacity ; i ++ )
            reverse[i] = 0;
        //从1开始，0表示不存在

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

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

//维护reverse的性质

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;
        reverse[i] = count+1;
        count++;

        shiftUp(count);
    }


  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;
        }
    }

 Item extractMax(){
        assert( count > 0 );

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

    int extractMaxIndex(){
        assert( count > 0 );

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

   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;
        }
    }


      void change( int i , Item newItem ){

        assert( contain(i) );
        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;
//            }

        int j = reverse[i];
        shiftUp( j );
        shiftDown( j );
    }

        bool contain( int i ){
        assert( i + 1 >= 1 && i + 1 <= capacity );
        return reverse[i+1] != 0;
    }

加入反向反向查找。

• 索引和数据分开。
• 加入反向数组查找

和堆相关的其他问题

系统优先队列

修改优先队列中优先值。

选择范围内优先攻击 问题

使用最小堆，使最小堆中元素一直小于等于100.当前100放入后，每次
新放入一个元素就将堆中最小的移除。使得整个堆一直保持着100个元素。等到100000个遍历完之后。剩下的就只有前100.

多路归并排序。

• 传统归并是分成两个
• 多路归并分成多个。

多路归并

四个组成一个最小堆。然后哪个是最小的移除并从哪个再提一个。

d越大层数越小。但是每次归并过程中比较元素个数多。

当n路归并只有一层时，他退化成了堆排序。

二叉堆 （Binary Heap）

d叉堆

完全树。d叉堆d的平衡。

最大堆- 最大索引堆 | 最小堆 - 最小索引堆

**堆的实现细节优化 **

ShiftUp 和 ShiftDown 中使用赋值操作替换swap操作
表示堆的数组从0开始索引
没有capacity的限制，动态的调整堆中数组的大小

最大最小队列并存：

数据结构中：最大堆，最小堆并存同时维护

堆的其他变种：

• 二项堆
• 斐波那契堆