堆排序 - 最后一块石头的重量

Leetcode 网址：https://leetcode-cn.com/problems/last-stone-weight/

主要思想：

• 每次从集合中选出质量最大的两个石头 —— 使用堆排序中的TopK策略
• 当选出的两块石头的质量不相同时， 将会放回一块 Math.abs(a-b) 质量的石头，然后重新进行排序
• 重复前两步，知道集合中只剩下一块或者没有石头

Java Solution:

public int lastStoneWeight(int[] stones) {
        //初始化堆排序队列
        Queue<Integer> pq = new PriorityQueue<>((a, b) -> b-a);
        for (int stone: stones) {
            pq.offer(stone);
        }

        while(pq.size() > 1) {
            int a = pq.poll();
            int b = pq.poll();

            if (a > b) pq.offer(a-b);
        }

        if (pq.isEmpty()) {
            return 0;
        }

        int result = pq.poll();
        return result;
    }

堆排序主要思想

堆排序相当于一个完全二叉树，根据二叉树的性质：

leftChildIdx = index2 + 1
rightChildIdx = index2 +2

一个最大堆所保证的条件是：

heap[i] >= heap[2i+1]
head[i] >= heap[2i+2]

初始化分堆思路：

• 由于堆是完全二叉树，我们只需要对每个父节点（含有叶子）进行堆排序即可
• 排序方法：
  • 对于每个父节点而言，找到最大或最小的节点，如果它不是父节点，则需要把它和父节点的值进行调换
  • 对于调换后的子节点而言，如果它也是父节点，则需要检测这个子节点时候也需要和它的子节点进去调换。可用递归实现此步骤
• 每当一个新的元素进入堆，将堆放在最后一个元素中，然后进行向上调整
• 每当一个元素从堆中删除。将最后一个元素放在当前删除的位置，然后进行向下调整。

public class HeapSort {
    private int [] dataList;

    public HeapSort(int [] inputList) {
        this.dataList = inputList;
        initHeap();
    }

    public void initHeap() {
        int size = dataList.length;
        for (int i = size/2 - 1; i >= 0; i--) {
            compareAndSwap(i);
        }
        System.out.println("Init complete: " + Arrays.toString(dataList));
    }

    private void compareAndSwap(int idx) {
        int size = dataList.length;

        int leftIdx = idx*2+1;
        int rightIdx = idx*2 + 2;

        int smallestIdx = idx;

        if (leftIdx < size && dataList[leftIdx] < dataList[idx]) {
            smallestIdx = leftIdx;
        }

        if (rightIdx < size && dataList[rightIdx] < dataList[smallestIdx]) {
            smallestIdx = rightIdx;
        }

        //swap
        if (smallestIdx != idx) {
            int tmp = dataList[idx];
            dataList[idx] = dataList[smallestIdx];
            dataList[smallestIdx] = tmp;

            //compareAndSwap the changed child
            compareAndSwap(smallestIdx);
        }

    }

    public int getRoot() {return dataList[0];}


    public void setRoot(int data) {
        if (dataList[0] >= data) return;
        System.out.println("New root: " + data + ", previous one is: " + dataList[0]);
        this.dataList[0] = data;

        compareAndSwap(0);

        System.out.println("Current result: " + Arrays.toString(dataList));


    }


}