排序算法之【堆排序】

目录

实现一个小顶堆，并提供了升序和降序的方法

堆排序方法测试

 LeetCode-215题

实现一个小顶堆，并提供了升序和降序的方法

/**
 * 小顶堆
 */
public class MinHeap {
    // 底层存放元素的容器
    private int[] container;

    // 元素个数
    private int size;

    /**
     * 获取升序排序后的结果
     */
    public int[] upSort(int[] nums) {
        heapIfy(nums);
        final int len = size;
        int[] result = new int[len];
        for (int i = 0; i < len; i++) {
            result[i] = poll();
        }
        return result;
    }

    /**
     * 获取降序排序后的结果
     */
    public int[] downSort(int[] nums) {
        heapIfy(nums);
        final int len = size;
        int[] result = new int[len];
        for (int i = len - 1; i >= 0; i--) {
            result[i] = poll();
        }
        return result;
    }

    /**
     * 堆化
     */
    private void heapIfy(int[] nums) {
        if (nums == null || nums.length == 0)
            return;
        size = nums.length;
        container = new int[size];
        System.arraycopy(nums, 0, container, 0, size);
        doHeapIfy();
    }

    private void doHeapIfy() {
        // 最后一个非叶子节点
        int lastNoLeafIndex = (size >> 1) - 1;
        // 从最后一个非叶子节点开始到根节点依次下潜
        for (int i = lastNoLeafIndex; i >= 0; i--) {
            siftDown(i);
        }
    }

    /**
     * 下潜
     */
    private void siftDown(int parent) {
        // 左右子节点
        int leftChild = (parent << 1) + 1;
        int rightChild = leftChild + 1;
        int min = parent;
        if (leftChild < size && container[min] > container[leftChild]) {
            min = leftChild;
        }
        if (rightChild < size && container[min] > container[rightChild]) {
            min = rightChild;
        }
        if (min != parent) {
            // 交换两位置的值，继续下潜
            swap(min, parent);
            siftDown(min);
        }
    }

    /**
     * 交换数组中i位置和j位置的值
     */
    private void swap(int i, int j) {
        if (container == null || container.length < 2 || i == j)
            return;
        container[i] = container[i] ^ container[j];
        container[j] = container[i] ^ container[j];
        container[i] = container[i] ^ container[j];
    }

    /**
     * 堆顶移除元素
     */
    public int poll() {
        int e = peek();
        // 交换第一个元素和最后一个元素
        swap(0, --size);
        // 下潜根元素
        siftDown(0);
        return e;
    }

    /**
     * 查看堆顶元素
     */
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("堆已空！");
        }
        return container[0];
    }

    /**
     * 是否没有元素了
     */
    public boolean isEmpty() {
        return size == 0;
    }
}

堆排序方法测试

import java.util.Arrays;

public class HeapSortTest {
    public static void main(String[] args) {
        int[] nums = {23, 12, 34, 42, 345, 56, 45, 34, 37, 43, 1, 23, 44, 67};
        MinHeap heap = new MinHeap();

        // 升序
        int[] upSortNums = heap.upSort(nums);
        // [1, 12, 23, 23, 34, 34, 37, 42, 43, 44, 45, 56, 67, 345]
        System.out.println(Arrays.toString(upSortNums));

        // 降序
        int[] downSortNums = heap.downSort(nums);
        // [345, 67, 56, 45, 44, 43, 42, 37, 34, 34, 23, 23, 12, 1]
        System.out.println(Arrays.toString(downSortNums));
    }
}

 LeetCode-215题

求数组中的第K个最大元素，这里使用的是小顶堆的实现方式，小顶堆大顶堆来实现都可以

class Solution {
    public int findKthLargest(int[] nums, int k) {
        MinHeap heap = new MinHeap();
        return heap.downSort(nums)[k - 1];
    }

    static class MinHeap {
        // 底层存放元素的容器
        private int[] container;

        // 元素个数
        private int size;

        /**
         * 获取升序排序后的结果
         */
        public int[] upSort(int[] nums) {
            heapIfy(nums);
            final int len = size;
            int[] result = new int[len];
            for (int i = 0; i < len; i++) {
                result[i] = poll();
            }
            return result;
        }

        /**
         * 获取降序排序后的结果
         */
        public int[] downSort(int[] nums) {
            heapIfy(nums);
            final int len = size;
            int[] result = new int[len];
            for (int i = len - 1; i >= 0; i--) {
                result[i] = poll();
            }
            return result;
        }

        /**
         * 堆化
         */
        private void heapIfy(int[] nums) {
            if (nums == null || nums.length == 0)
                return;
            size = nums.length;
            container = new int[size];
            System.arraycopy(nums, 0, container, 0, size);
            doHeapIfy();
        }

        private void doHeapIfy() {
            // 最后一个非叶子节点
            int lastNoLeafIndex = (size >> 1) - 1;
            // 从最后一个非叶子节点开始到根节点依次下潜
            for (int i = lastNoLeafIndex; i >= 0; i--) {
                siftDown(i);
            }
        }

        /**
         * 下潜
         */
        private void siftDown(int parent) {
            // 左右子节点
            int leftChild = (parent << 1) + 1;
            int rightChild = leftChild + 1;
            int min = parent;
            if (leftChild < size && container[min] > container[leftChild]) {
                min = leftChild;
            }
            if (rightChild < size && container[min] > container[rightChild]) {
                min = rightChild;
            }
            if (min != parent) {
                // 交换两位置的值，继续下潜
                swap(min, parent);
                siftDown(min);
            }
        }

        /**
         * 交换数组中i位置和j位置的值
         */
        private void swap(int i, int j) {
            if (container == null || container.length < 2 || i == j)
                return;
            container[i] = container[i] ^ container[j];
            container[j] = container[i] ^ container[j];
            container[i] = container[i] ^ container[j];
        }

        /**
         * 堆顶移除元素
         */
        public int poll() {
            int e = peek();
            // 交换第一个元素和最后一个元素
            swap(0, --size);
            // 下潜根元素
            siftDown(0);
            return e;
        }

        /**
         * 查看堆顶元素
         */
        public int peek() {
            if (isEmpty()) {
                throw new RuntimeException("堆已空！");
            }
            return container[0];
        }

        /**
         * 是否没有元素了
         */
        public boolean isEmpty() {
            return size == 0;
        }
    }
}