数据结构算法之堆排序

关于树和二叉树介绍以及遍历可以查看之前写的两篇文章
树的简单介绍和二叉树的遍历
二叉树

最大堆和最小堆

最大堆：根结点的键值是所有堆结点键值中最大者，且每个结点的值都比其孩子的值大。

最大堆.png

最小堆：根结点的键值是所有堆结点键值中最小者，且每个结点的值都比其孩子的值小。

最小堆.png

堆总是一颗完全二叉树

数组存储最大堆

image.png

此时父节点 parent(i)=i/2;
left child(i)=2i;
right child(i)=2i+1;

插入数据的时候需要将大的值往上浮，这时候我们需要一个shiftUp(上浮)操作，简单说比如插入一个52的值，首先我们把它放上去

image.png

这时候，52比16大，所以52和16交换位置，之后52与它的父节点41比较，因为52>41所以再次交换位置

image.png

   void shiftUp(int k) {
        while (k > 1 && data[k / 2] < data[k]) {
            std::swap(data[k / 2], data[k]);
            k /= 2;
        }
    }
    //算法复杂度O(nlogn)
    void insert(E e) {
        assert(count + 1 <= capacity);
        data[count + 1] = e;
        count++;
        shiftUp(count);
    }

取出元素

最大堆取出元素取出的是最大的元素，也就是最大堆中的根节点，也就是上图的62这个元素，取出之后需要将最后一个元素，也就是上图的16放到62的位置，原本16的位置设置null,然后这时候要保持最大堆性质就需要进行shiftDown操作

image.png

首先16和52与30判断，我们会发现，16比它们都小，这时候，我们判读左右节点，我们会发现52>30，所以52和16交换，依次轮推，16会再次与41交换

image.png

    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 += 1;
            }
            if (data[k] >= data[j]) {
                break;
            }
            swap(data[k], data[j]);
            k = j;
        }
    }
    E extractMax() {
        assert(count > 0);
        E e = data[1];
        swap(data[1], data[count]);
        count--;
        shiftDown(1);
        return e;
    }

Heapify:对已有的数组进行shiftDown

image.png

Heapify过程呢，其实就是倒着shiftDown的过程。比如上图所有蓝色的点，实际它们就是一个最大堆性质了，首先我们找到最后一个叶子结点的位置(n/2),这里实际就是10/2=5这个位置，因为5这个位置的值是22<62所以交换位置，第4位置和第8，9位置比较，因为13<30<41，所以41和13交换位置，剩下依次推论就可以了

image.png

最后结果.png

    //Heapify的过程，算法复杂度O(n)
    MaxHeap(E arr[], int n) {
        data = new E(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<class T>
void headSort1(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();
    }
}

template<class T>
void headSort2(T arr[], int n) {
    MaxHeap<T> maxHeap = MaxHeap<T>(arr, n);
    //从小到大
    for (int i = n - 1; i >= 0; i--) {
        arr[i] = maxHeap.extractMax();
    }
}
    //Heapify的过程，算法复杂度O(n)
    MaxHeap(E arr[], int n) {
        data = new E(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);
        }
    }
  E extractMax() {
        assert(count > 0);
        E e = data[1];
        swap(data[1], data[count]);
        count--;
        shiftDown(1);
        return e;
    }

原地堆排序

上述代码我们不难发现，我们对原数组排序的时候开辟了一块内存空间，其实我们完全可以在原地(不开辟内存空间)进行排序

image.png

parent(i)=(i-1)/2
left child(i)=2i+1;
right child(i)=2i+2

其实就是shiftDown+heapify操作，只是这里的i是从0开始而不是从1开始

template<class T>
void _shiftDown(T arr,int n,int k){
    while (2 * k+1<= n) {
        int j = 2 * k+1;//在此轮循中，data[k]和data[j]交换位置
        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<class T>
void headSort(T arr[], int n) {
    //第一个非叶子结点的索引
    for (int i = (n - 1) / 2; i >= 0; i--) {
        _shiftDown(arr, n, i);
    }
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        _shiftDown(arr,i, 0);
    }

完整代码

#ifndef NDK_PRIORITYQUEUE_H
#define NDK_PRIORITYQUEUE_H

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

#define TAG "TAG"
#define LOGE(...)  __android_log_print(ANDROID_LOG_ERROR,TAG,__VA_ARGS__)
//在n个元素选出前M个元素 优先队列nlogn 出队：选出优先级最高的
using namespace std;

template<class E>
class MaxHeap {
private:
    E *data;
    int count;
    int capacity;

    void shiftUp(int k) {
        while (k > 1 && data[k / 2] < data[k]) {
            std::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 += 1;
            }
            if (data[k] >= data[j]) {
                break;
            }
            swap(data[k], data[j]);
            k = j;
        }
    }

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

    //Heapify的过程，算法复杂度O(n)
    MaxHeap(E arr[], int n) {
        data = new E(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);
        }
    }

    ~MaxHeap() {
        delete[] data;
    }

    int size() {
        return count;
    }

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

    //算法复杂度O(nlogn)
    void insert(E e) {
        assert(count + 1 <= capacity);
        data[count + 1] = e;
        count++;
        shiftUp(count);
    }

    E extractMax() {
        assert(count > 0);
        E e = data[1];
        swap(data[1], data[count]);
        count--;
        shiftDown(1);
        return e;
    }
};
template<class T>
void _shiftDown(T arr,int n,int k){
    while (2 * k+1<= n) {
        int j = 2 * k+1;//在此轮循中，data[k]和data[j]交换位置
        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<class T>
void headSort(T arr[], int n) {
    //第一个非叶子结点的索引
    for (int i = (n - 1) / 2; i >= 0; i--) {
        _shiftDown(arr, n, i);
    }
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        _shiftDown(arr,i, 0);
    }

}


template<class T>
void headSort1(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();
    }
}

template<class T>
void headSort2(T arr[], int n) {
    MaxHeap<T> maxHeap = MaxHeap<T>(arr, n);
    //从小到大
    for (int i = n - 1; i >= 0; i--) {
        arr[i] = maxHeap.extractMax();
    }
}

#endif // NDK_PRIORITYQUEUE_H