堆排序/priority_queue的底层数据结构

二叉堆是一颗完全二叉树，使用数组来存储这个二叉堆的元素，效率最高，通过公式可以计算出一个下标的元素的父节点的下标以及两个子节点的下标。

当前下标元素的两个子节点的下标计算：

left=index*2+1;

right=index*2+2;

当前下标的父节点的下标计算：

parent=(index-1)/2;

往二叉堆(数组)中添加元素的原理

把新元素插入到二叉堆的第一个空闲的位置，然后通过公式计算父亲节点，不断的和父亲节点比较，往上浮，上浮到父节点大于等于新元素的位置就可以。

删除二叉堆对顶元素的原理

不删除对顶元素，而是用最后一个元素替换对顶元素，删除最后一个元素，然后再让对顶元素下沉，下沉的节点应该要和左右子节点比较大的节点交换，这样对顶才是最大值，一直下沉到左右子节点都小于当前节点即可。

堆化的原理

需求：将一个乱序的数组按照大顶堆或者小顶堆的存储方式，重新存储在数组中。

根据完全二叉树存储在数组中的特点，就是数组中前一半需要存储非叶子节点，后一半存储叶子节点的特点。

只需要对乱序数组所有的非叶子节点下沉就可以形成一颗二叉堆。

时间复杂度：O(n)----和非叶子节点的高度有关。

heapify(vector<T>& vec) {
	maxhpVec.assign(vec.begin(),vec.end());
	for (int i = lastNoLeafIndex(); i >= 0; --i) {
		siftDown(i);
	}
}
void siftDown(int index) {
	T temp = maxhpVec[index];
	int leftIndex = leftChildIndex(index);
	int rightIndex = rightChildIndex(index);
	int n = maxhpVec.size();
	while (leftIndex < n) {
		int maxIndex = leftIndex;
		if (rightIndex < n) {
			if (maxhpVec[leftIndex] < maxhpVec[rightIndex])
				maxIndex = rightIndex;
		}
 
		if (maxhpVec[maxIndex] > temp) {
			maxhpVec[index] = maxhpVec[maxIndex];
			index = maxIndex;
			leftIndex = leftChildIndex(index);
			rightIndex = rightChildIndex(index);
		}
		else break;
	}
	maxhpVec[index] = temp;
}

如果把一个数组放入一个二叉堆中，时间复杂度为O(nlogn)

堆排序

堆排序是在完成堆化操作之后，堆元素进行的排序。

堆排序实现

直接优先队列

堆化之后第一个元素不断下沉

void max_heapify(vector<int> arr, int index, int len) {
    //建立父节点指标和子节点指标
    int left_index = index*2+1;
    int right_index=index*2+2;
    while (left_index<len) { //若子节点指标在范围内才做比较
        int max_index=left_index;
        if(right_index<len&&arr[left_index]<arr[right_index]){
            max_index=right_index;
        }
        if(arr[max_index]>arr[index]){ //否则交换父子内容再继续子节点和孙节点比较
            swap(arr[index],arr[max_index]);
            index=max_index;
            left_index = index*2+1;
            right_index=index*2+2;
        }
        else break;
    }
}
void heap_sort(vector<int>& arr, int len) {
    //初始化，i从最后一个父节点开始调整
    for (int i = (len-1-1)/2; i >= 0; i--)
        max_heapify(arr, i, len);
    //先将第一个元素和已经排好的元素前一位做交换，再从新调整(刚调整的元素之前的元素)，直到排序完毕
    for (int i = len - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        max_heapify(arr, 0, i - 1);
    }
}