时间复杂度：O(Nlog(N))
额外空间复杂度：O(1)
是否可实现稳定性：否
思路：
把数组逻辑上看成一个二叉树，数组下标和二叉树中的位置逻辑对应。
在二叉树中的父节点p和孩子l，r有对应关系(在数组中的下标的对应关系)
l = 2*index +1 r = 2 * index +2 这是已知父节点index的下标，求孩子节点的下标
index = (index-1)/2 这是已知孩子节点index，求父节点的下标
堆排序主要是通过大根堆实现的，何为大根堆呢？大根堆是一个完全二叉树，根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者，找到大根堆后，把数组对应的逻辑二叉树最右下角的节点和根节点交换位置，这样最大的数就放到数组的最后了，然后数组的下标-1，再把此时的根节点做沉底操作，沉底操作就是如果换位置之后的根节点的值依然是最大值就不用换位置，如果比自己的孩子节点小，就和孩子节点中的较大的一个交换位置，直到沉底，然后循环这个过程。
如果还不懂结合代码注释理解
代码：
public static void heapSort(int[] arr){
if (arr==null||arr.length<2){
return;
}
//建立一个size=数组长度的大根堆，这个大根堆的size就是数组长度
int size = arr.length;
//建立大根堆的过程
for (int i = 0;i<arr.length;i++){
heapInsert(arr,i);
}
//交换0位置和最后的数，因为在建立大根堆以后0位置的数已经是所有数最大
swap(arr,0,--size);
//循环，做0和--size（最后位置，就是每次size缩小后的最后位置）的交换
while (size>0){
//沉底操作
heapify(arr,0,size);
//交换
swap(arr,0,--size);
}
}
public static void heapify(int[] arr,int index,int size){
//当前结点的左孩子
int left = 2*index+1;
//判断左孩子是否小宇size，小于就说明数组没有越界，如果左孩子越界有孩子肯定越界
while (left<size){
//设置一个最大的变量，他的初始值是左孩子和右孩子中的最大值
int largest = left+1<size&&arr[left+1]>arr[left] ? left+1 : left;
//判断当前结点和孩子节点最大值的大小，更新largest的值
largest = arr[largest] > arr[index] ? largest:index;
//如果largest还是index，说明当前结点的值就是此时大根堆的最大值
if (largest == index ){
break;
}
//否则 交换
swap(arr,largest,index);
//然后index变成largest在大根堆中的位置，继续下沉
index = largest;
left = 2*index+1;
}
}
public static void heapInsert(int[] arr, int index){
//这个判断条件两个作用，
//第一个作用如果当前结点比父节点的值大，就交换
//直到index=（index-1）/2说明到了根节点跳出循环
while (arr[index]>arr[(index-1)/2]){
swap(arr,index,(index-1)/2);
index = (index-1)/2;
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
扩展（堆的相关应用）：
题目1：
求实时中位数.png
思路：
建立一个大根堆，一个小根堆，将数组的数加入到这两个堆里，加入的规则是，选择第一个数字进入的堆，任意选，大根堆小根堆都行，比如加入了大根堆，然后再加一个数，每次加数前，都查看大根堆和小根堆的大小差距，如果差距大于一，就把当前堆的堆顶加入到另一个堆。
在这里注意，优先级队列，默认小根堆，如果想把它变成大根堆，需要定义比较器，传入创建的优先级队列。比较器大于零升序，小根堆；小于零，降序，大根堆。
代码：
public static class MedianHolder {
private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new MaxHeapComparator());
private PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(new MinHeapComparator());
private void modifyTwoHeapsSize() {
if (this.maxHeap.size() == this.minHeap.size() + 2) {
this.minHeap.add(this.maxHeap.poll());
}
if (this.minHeap.size() == this.maxHeap.size() + 2) {
this.maxHeap.add(this.minHeap.poll());
}
}
public void addNumber(int num) {
if (this.maxHeap.isEmpty()) {
this.maxHeap.add(num);
return;
}
if (this.maxHeap.peek() >= num) {
this.maxHeap.add(num);
} else {
if (this.minHeap.isEmpty()) {
this.minHeap.add(num);
return;
}
if (this.minHeap.peek() > num) {
this.maxHeap.add(num);
} else {
this.minHeap.add(num);
}
}
modifyTwoHeapsSize();
}
public Integer getMedian() {
int maxHeapSize = this.maxHeap.size();
int minHeapSize = this.minHeap.size();
if (maxHeapSize + minHeapSize == 0) {
return null;
}
Integer maxHeapHead = this.maxHeap.peek();
Integer minHeapHead = this.minHeap.peek();
if (((maxHeapSize + minHeapSize) & 1) == 0) {
return (maxHeapHead + minHeapHead) / 2;
}
return maxHeapSize > minHeapSize ? maxHeapHead : minHeapHead;
}
}
public static class MaxHeapComparator implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
if (o2 > o1) {
return 1;
} else {
return -1;
}
}
}
public static class MinHeapComparator implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
if (o2 < o1) {
return 1;
} else {
return -1;
}
}
}
// for test
public static int[] getRandomArray(int maxLen, int maxValue) {
int[] res = new int[(int) (Math.random() * maxLen) + 1];
for (int i = 0; i != res.length; i++) {
res[i] = (int) (Math.random() * maxValue);
}
return res;
}
// for test, this method is ineffective but absolutely right
public static int getMedianOfArray(int[] arr) {
int[] newArr = Arrays.copyOf(arr, arr.length);
Arrays.sort(newArr);
int mid = (newArr.length - 1) / 2;
if ((newArr.length & 1) == 0) {
return (newArr[mid] + newArr[mid + 1]) / 2;
} else {
return newArr[mid];
}
}
public static void printArray(int[] arr) {
for (int i = 0; i != arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
boolean err = false;
int testTimes = 200000;
for (int i = 0; i != testTimes; i++) {
int len = 30;
int maxValue = 1000;
int[] arr = getRandomArray(len, maxValue);
MedianHolder medianHold = new MedianHolder();
for (int j = 0; j != arr.length; j++) {
medianHold.addNumber(arr[j]);
}
if (medianHold.getMedian() != getMedianOfArray(arr)) {
err = true;
printArray(arr);
break;
}
}
System.out.println(err ? "Oops..what a fuck!" : "today is a beautiful day^_^");
}
题目二：
金条问题.png
思路：
相当于把传入的数组建立一个小根堆，返回叶子结点的和。为什么这么做对，贪心思想，把建立的小根堆如果元素大于两个，就弹出两个（每次弹出后结构自动调整，优先级队列实现），取和cur，num+=cur，然后再把cur装入小根堆，依次下去，即可求出结果。
代码：
public static int lessMoney(int[] arr) {
PriorityQueue<Integer> pQ = new PriorityQueue<>();
for (int i = 0; i < arr.length; i++) {
pQ.add(arr[i]);
}
int sum = 0;
int cur = 0;
while (pQ.size() > 1) {
cur = pQ.poll() + pQ.poll();
sum += cur;
pQ.add(cur);
}
return sum;
}
public static void main(String[] args) {
// solution
int[] arr = {6, 7, 8, 9};
System.out.println(lessMoney(arr));
}
问题3：
获利最大.png
思路：
建立一个大根堆，用来存利润，建立一个小根堆，用来记录最小花费，把所有的项目加入到小根堆中，然后把当前启动资金能满足的项目加入到大根堆中，弹出大根堆的堆顶，加到本金中，即第二次的本金=原来的本金+利润，注意在这里利润就是扣除当前项目花费后能赚的前，比如启动资金是100，当前项目花费是50，利润是100，做完这个项目后身上的钱=100 +（150-50） = 200；依次执行下去，就可得到最大利润
代码：
public static class Node {
public int p;
public int c;
public Node(int p, int c) {
this.p = p;
this.c = c;
}
}
public static class MinCostComparator implements Comparator<Node> {
@Override
public int compare(Node o1, Node o2) {
return o1.c - o2.c;
}
}
public static class MaxProfitComparator implements Comparator<Node> {
@Override
public int compare(Node o1, Node o2) {
return o2.p - o1.p;
}
}
public static int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
Node[] nodes = new Node[Profits.length];
for (int i = 0; i < Profits.length; i++) {
nodes[i] = new Node(Profits[i], Capital[i]);
}
PriorityQueue<Node> minCostQ = new PriorityQueue<>(new MinCostComparator());
PriorityQueue<Node> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());
for (int i = 0; i < nodes.length; i++) {
minCostQ.add(nodes[i]);
}
for (int i = 0; i < k; i++) {
while (!minCostQ.isEmpty() && minCostQ.peek().c <= W) {
maxProfitQ.add(minCostQ.poll());
}
if (maxProfitQ.isEmpty()) {
return W;
}
W += maxProfitQ.poll().p;
}
return W;
}
