快速手写堆排序

问题描述

[[1,2],[2,3],[4,5],[7,9],[0,3],[0,1],[1,1]]

这是坐标输入，请按照离原点的距离对坐标进行排序，要求使用手写的堆排序算法

划分

划分业务：distance()计算距离，swap()负责交换位置，heapify()将元素负责堆化，buildHeap()负责调用heapify()建堆,heapSort是唯一对外提供的调用接口，负责排序的整体业务。

理解

只要所有父结点比两个子节点都不小于，那么这就是一个堆，根据堆很好可以获得最大值，我们每次把堆顶的元素拿出来，再把剩余元素重新修整成堆，就又得到了剩下的最大值，得以排序

实际上实现是数组，因为两个儿子的坐标是2n+1和2n+2

每次堆顶和数组当前最后的元素交换（意思是最大的放在后面）这时只有堆顶这一个元素不符合堆的结构，我们只要将其一个元素堆化即可，以较小代价修复了堆，所以又得到了剩余的 最大值

代码

package wang.xk;

public class PointHeapSort {
    private int[][] tree = null;

    public static void main(String[] args) {
        int[][] data = {{1, 2}, {2, 3}, {4, 5}, {7, 9}, {0, 3}, {0, 1}, {1, 1}};
        //int[][] data = {{1, 1}, {0, 3}, {4, 1}, {3, 2}, {5, 2}, {8, 1}, {1, 7}};

        new PointHeapSort().heapSort(data);
        for (int i = 0; i < data.length; i++) {
            int[] tt = data[i];
            for (int i1 = 0; i1 < tt.length; i1++) {
                System.out.print(tt[i1] + " ");
            }
            System.out.println();
        }
    }

    private void buildHeap(int[][] data) {
        this.tree = data;
        for(int i=tree.length-1;i>=0;i--){
            heapify(i,tree.length);
        }
    }

    private void heapify(int ind,int n) { // n为堆中元素个数
        if (2 * ind + 1 >= n) { // 至少需要有个左儿子
            return;
        }
        int left = 2 * ind + 1;
        int right = 2 * ind + 2;
        int maxId; // 找到左右最大的
        if (right < n) {
            maxId = distance(tree[right]) > distance(tree[left]) ? right : left;
        } else {
            maxId = left;
        }
        if(distance(tree[maxId])>distance(tree[ind])){ // 可以下沉
            swap(maxId,ind,tree);
            heapify(maxId,n);
        }
    }

    public void heapSort(int[][] data) {
        buildHeap(data);
        for(int i=tree.length-1;i>0;i--){
            swap(0,i,tree);
            heapify(0,i);
        }
    }

    private void swap(int i,int j,int[][] points){
        int[] temp = points[i];
        points[i] = points[j];
        points[j] = temp;
    }

    private int distance(int[] point){
        return point[0]*point[0] + point[1]*point[1];
    }
}