数据结构与算法详解——堆篇（附c++实现代码）

堆

堆其实可以看成是完全二叉树，即除了最后一层其他层全满，最后一层的叶子结点靠左边的二叉树。
其次，堆的每个结点的值必须大于等于（或者小于等于）其子树的中每个结点的值，根据这个性质，我们可以知道堆的根结点的值是整个堆中最大（或者最小的），也称为大顶堆（小顶堆）。

堆的实现

存储

之前在二叉树那一篇中提到过，完全二叉树非常适合用数组存储（以上图大顶堆为例）：
第一种：下标从1开始存储，在不超边界的情况下，假设当前结点的下标为i，左子树的下标为i*2，右子树的下标为i*2+1，父节点的下标为i/2。

第二种：下标从0开始存储，在不超边界的情况下，假设当前结点的下标为i，左子树的下标为i*2+1，右子树的下标为i*2+2，父节点的下标为(i-1)/2。

插入

往堆插入一个元素，为了继续满足完全二叉树的特点，所以我们将这个元素加在堆的末尾或者说数组的末尾。
其次，还需要满足大顶堆(小顶堆)的特点，本文以大顶堆为例。要保持大顶堆的特点，需要进行堆化，堆化又分为自上而下和自下而上。
自上而下的堆化：拿当前结点n和左右孩子比较，如果左右孩子得值有比n大的，那么把大的那个结点的值与n进行交换，从大的孩子结点继续往下进行上面的比较，直到叶子结点；如果左右孩子没有比n大的就直接结束。因为是一直和孩子结点进行比较，所以是从上往下的。
自下而上的堆化：拿当前结点n和父节点比较，如果比父节点大，那么就交换值，从父节点开始，直到根节点。如果没有比父节点大就直接结束。和上面差不多，不过不是和孩子结点比较，而是和父节点进行比较，所以是从下往上的。
这里我们将一个结点插入到末尾，所以是从下往上进行堆化，来看下面这个例子：

我们插入21，加到堆的末尾，然后开始自下而上的堆化：21>父节点2所以交换值，然后接着在父节点的位置比较21>根节点20所以交换值，到根节点了结束，可以看到堆化后继续保持了大顶堆的特点。
插入的代码如下：

void insert(T data) {
		//size是已经装了的元素个数，capacity是数组申请的空间大小
		if (size >= capacity)return;	//堆满了，这里没有写扩容的逻辑
		++size;	
		arr[size] = data;
		int i = size;
		while ((i - 1) / 2 > 0 && arr[(i - 1) / 2] < arr[i]) {	//(i - 1) / 2是父节点的下标，自下而上堆化
			std::swap(arr[(i - 1) / 2], arr[i]);
			i = (i - 1) / 2;
		}

删除堆顶元素

删除堆顶元素我们需要用到自上而下的堆化，这里我们将最后一个元素与堆顶元素交换，然后再从根节点自上而下堆化：

void removeMax() {
		if (size == 0)return;
		arr[0] = arr[size];		//将最后一个元素换到根节点的位置
		--size;
		heapify(size, 1);//然后自上而下堆化
	}

	void heapify(int n, int i) {	//自上而下堆,n表示数组最末尾的下标，从下标i开始进行堆化
		while (1) {
			int maxPos = i;
			if (i * 2 + 1 >= n && arr[i] < arr[i * 2 + 1])maxPos = i * 2 + 1;
			if (i * 2 + 2 >= n && arr[maxPos] < arr[i * 2 + 2])maxPos = i * 2 + 2;
			if (maxPos == i)break;
			std::swap(arr[i], arr[maxPos]);
			i = maxPos;
		}
	}

完整代码

#ifndef HEAP_H
#define HEAP_H

template <typename T>
class heap {
private:
	T *arr;
	int capacity;
	int size;
public:
	heap(int capacity) {
		arr = new T[capacity];
		this->capacity = capacity;
		size = 0;
	}
	~heap() {
		delete[] arr;
	}

	void insert(T data) {
		if (size >= capacity)return;	//堆满了，这里没有写扩容的逻辑
		++size;
		arr[size] = data;
		int i = size;
		while ((i - 1) / 2 > 0 && arr[(i - 1) / 2] < arr[i]) {	//(i - 1) / 2是父节点的下标，自下而上堆化
			std::swap(arr[(i - 1) / 2], arr[i]);
			i = (i - 1) / 2;
		}
	}

	void removeMax() {
		if (size == 0)return;
		arr[0] = arr[size];		//将最后一个元素换到根节点的位置
		--size;
		heapify(size, 1);//然后自上而下堆化
	}

	void heapify(int n, int i) {	//自上而下堆,n表示数组最末尾的下标，从下标i开始进行堆化
		while (1) {
			int maxPos = i;
			if (i * 2 + 1 >= n && arr[i] < arr[i * 2 + 1])maxPos = i * 2 + 1;
			if (i * 2 + 2 >= n && arr[maxPos] < arr[i * 2 + 2])maxPos = i * 2 + 2;
			if (maxPos == i)break;
			std::swap(arr[i], arr[maxPos]);
			i = maxPos;
		}
	}
};


#endif

堆的应用

堆排序

有了上面删除堆顶的元素后，应该能想到堆排序就是不断删除堆顶元素，那么每一次最大的元素都会被交换到数组的末尾，整个数组就会排好序了。但是一开始输入的数组并不满足大顶堆的特点，所以我们还需要先建堆。

1. 建堆
2. 删除堆顶元素直到堆剩一个元素

代码直接贴出来了：

#ifndef HEAPSORT_H
#define HEAPSORT_H

//这里数组的起始坐标从0开始，而不是从1开始，左孩子下标=i*2+1，右孩子下标=i*2+2，大顶堆
template <typename T>
class heapSort {
public:
	static void sort(T arr[],int n);
private:
	static void buildHeap(T arr[],int n);
	static void heapify(T arr[], int n, int i);
};

template <typename T>
void heapSort<T>::sort(T arr[], int n) {		//static只需要加在类定义里，类定义外面的函数定义前不能写static
	if (n <= 1)return;
	buildHeap(arr, n);	//建堆
	int k = n - 1;		//数组的最后一个元素
	while (k > 0) {
		std::swap(arr[0], arr[k]);	//将大顶堆最大的元素arr[0]放到数组的末尾arr[k]
		heapify(arr, --k, 0);	//将剩余的元素重新堆化，注意--k，因为末尾的元素已经是有序的了，所以堆化不用考虑末尾的元素了。
	}
}

template <typename T>
void heapSort<T>::buildHeap(T arr[], int n) {
	for (int i = n/ 2 - 1  ; i >= 0; i--)	//n / 2 - 1是最后一个叶子结点的父节点的下标，从这个结点开始从上往下堆化，直到根结点
		heapify(arr, n-1, i);
}

//n表示数组要堆化的最后的下标，注意n不是arr的长度
//i表示自上而下堆化的起始下标，即从i开始往下堆化
template <typename T>
void heapSort<T>::heapify(T arr[], int n, int i) {
	while (1) {
		int maxPos = i;
		if (i * 2 + 1 <= n && arr[i] < arr[i * 2 + 1])	//和左孩子比较
			maxPos = i * 2 + 1;
		if (i * 2 + 2 <= n && arr[maxPos] < arr[i * 2 + 2])	//和右孩子比较，注意这里是和arr[maxPos]比较
			maxPos = i * 2 + 2;
		if (maxPos == i)break;
		std::swap(arr[i], arr[maxPos]);
		i = maxPos;
	}

}

#endif

先看看建堆buildHeap函数，很简单，就是从最后一个叶子结点的父节点开始自上而下堆化，直到根节点。注意不能从根节点开始自上而下堆化，因为需要先保证下面的每个子堆都是大顶堆，根节点再进行自上而下堆化才能保证整个堆是大顶堆。
这里可能有个疑惑为什么buildHeap里父节点的下标是(n/ 2 - 1)，前面不是说了是（i-1）/2吗？因为这里的n是数组的长度，而 i 是数组最末尾的下标，n=i+1，代入进去就是一样的了。
自上而下堆化和上面删除对顶元素的代码基本一致，就是参数要把数组传进去。
堆排序的算法分析：

1. 堆排序是一种原地排序算法
2. 堆排序是非稳定的排序算法，因为堆顶元素会和最后一个元素交换，其次堆化时也会产生交换可能会改变相同元素的前后顺序。
3. 堆排序的时间复杂度为O(nlogn)

堆排序为什么没有快排性能好：

1. 堆排序访问数组是跳着下标访问的，例如堆化时访问父节点（i-1）/2或者访问孩子节点i*2+1、i*2+2，对CPU缓存不友好；而快排是局部顺序访问的，对CPU缓存友好
2. 对于同样的数据，堆排序算法的数据交换次数要多于快速排序。第一步建堆就打乱了原有的数据顺序，可能原来有序的数据因此变得无序。

topK问题

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
leetcode的链接：215. 数组中的第K个最大元素
其中一个比较好的思路就是使用堆，最大的K个元素使用小顶堆，最小的K个元素使用大顶堆。以这题为例，求最大的K个元素，就可以建立K个元素的小顶堆，堆顶就是K个元素中最小的，然后遍历数组，将数组的元素与堆顶比较，如果数组元素>堆顶元素，那么就将堆顶元素删除，将这个数组元素插入堆；如果数组元素<堆顶元素就不做处理，继续遍历数组。遍历完成后，小顶堆里的K个元素就是最大的K个元素了，堆顶就是第K大的元素。
下面看看leetcode的提交代码：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        if(nums.empty())
            return 0;
        priority_queue<int,vector<int>,greater<int>> que; //注意这是小顶堆
        for(auto n:nums){
            que.push(n);
            if(que.size()> k)   //小顶堆保持数量为k
                que.pop();
        }
        return que.top();
    }
};

这里使用了priority_queue优先队列，可以看成是堆，int表示数据类型，vector表示装数据的容器，greater表示这是小顶堆。
思路基本相同，但是这里是将所有元素都放入堆中，如果堆的数量大于k就删除堆顶元素。最后小顶堆的元素就是最大的K个元素了，堆顶元素是最小的，也就是第K大的元素。
这里也可以按照上面的思路写，也就是如果数组元素>堆顶元素，才将这个元素插入并删除堆顶元素。但是一开始要将k个元素先建堆，再遍历剩下的数组元素：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        if(nums.empty())
            return 0;
        priority_queue<int,vector<int>,greater<int>> que; //注意这是小顶堆
        int i=0;
        for(;i<k;i++)
            que.push(nums[i]);
        for(;i<nums.size();i++)
            if(nums[i]>que.top()){
                que.push(nums[i]);
                que.pop();
            }
        return que.top();
    }
};

遍历数组需要O(n)的时间复杂度，一次堆化操作需要的时间复杂度为O(logK)，所以最坏情况下所有元素都要入堆一次，因此最坏情况下时间复杂度为O(nlogK)。

求中位数

leecode链接：剑指 Offer 41. 数据流中的中位数
简单来说，就是一个动态数据集合求中位数，addNum可以往数据集合里添加数据，findMedian返回中位数。这里我们可以用一个大顶堆，一个小顶堆解决，大顶堆的数据都比小顶堆的数据要小，如果是偶数个数据，两个堆存储的数据数量一致，那么中位数就是（两个堆顶的和 / 2）；如果是奇数个数据，大顶堆存储多一个数据，那么中位数就是大顶堆堆顶（也可以是小顶堆存储多一个数据，中位数就是小顶堆堆顶）。

class MedianFinder {
private:
    priority_queue<int> left;   //默认大顶堆
    priority_queue<int,vector<int>,greater<int>> right; //小顶堆
public:
    /** initialize your data structure here. */
    MedianFinder() {

    }
    
    void addNum(int num) {
    //数据放在left之前要先放入right过滤一下，确保放入left的数据比right中的所有数据要小
        right.push(num);	
        left.push(right.top());
        right.pop();
        if(left.size()>right.size()+1){
            right.push(left.top());
            left.pop();
        }
    }
    
    double findMedian() {
        if(left.size()>right.size())
            return left.top();
        return (left.top()+right.top())/2.0;
    }
};

这里我们采用【如果是奇数个数据，大顶堆存储多一个数据，那么中位数就是大顶堆堆顶】，所以要添加数据优先添加到大顶堆left上，但是不能直接将num放入left中，因为num可能比right中的数据要大，无法保持【left的数据都比right的数据要小】；所以需要将num放入right中过滤，再将right的堆顶也就是最小的元素放入left中，right再pop出堆顶，这样才能保证添加到left中的数据比right中所有数据都要小。也就是这三行代码：（right添加num，删除堆顶，数量无变化，left添加了right的堆顶，所以left添加了一个数据）

		right.push(num);	
        left.push(right.top());
        right.pop();

数据优先添加到left里，但是要维持：

1. 偶数个数据时，left.size()=right.size()
2. 奇数个数据时，left.size()=right.size()+1

我们在添加数据时优先放入left里，所以left的数量会越来越多，但是left.size()不能超过(right.size()+1)，如果超过的话，就要把left的堆顶添加到right上，并且left删除堆顶（left的堆顶是left中最大的，这样可以保证right的数据比left中所有数据大）。此外这样操作后，left和right中数据的数量就会相同（left减少一个数据，right添加一个数据）。也就是这几行代码：

	if(left.size()>right.size()+1){
            right.push(left.top());
            left.pop();
    }

添加数据就结束了，中位数的代码应该直接能看懂了。