堆排序HeapSort

引用算法导论中对于堆排序的描述：

Like merge sort,but unlike insertion sort, heapsort’s running time is . Like insertion sort,
but unlike merge sort, heapsort sorts in place: only a constant number of array
elements are stored outside the input array at any time. Thus, heapsort combines
the better attributes of the two sorting algorithms we have already discussed

• 堆排序是一种原地排序
• 堆排序的时间复杂度为
• 堆排序是一种不稳定的排序

在介绍堆排序之前，先介绍堆这一种数据结构,以最大堆为例：

• 堆可以看做是一个完全二叉树，从上向下，从左向右填充。
• 父节点大于等于孩子节点。

堆排序可使用数组实现的完全二叉树结构，对数组索引为i的节点，有如下索引关系

• 父亲节点索引 parent(i)=(i-1)/2
• 左孩子索引 left(i)=i*2+1
• 右孩子索引 right(i)=i*2+2

heapify

假设对于数组data下标为k的节点，二叉树 的left(k)子树和right(k)子树已经了满足堆的性质，但是data[k] 可能小于left(k)或right(k)，这时候需要将k这个下标对应的节点向下调整。这个过程称之为heapify

如下图所示，数组索引值为1的节点对应的元素为4，heapify执行时会将它与其较大的孩子节点交换，通过两次交换，最终满足了堆的特性

heapify

heapify的时间复杂度为

buildMaxHeap

使用一个数组构建出一个二叉堆的方式是从最后一个元素的parent开始直到第零个元素依次调用之前提到的heapify。
这个过程是一个从右到左，从上到下的调整过程
这个过程的时间复杂度为

heapSort

首先使用buildMaxHeap构建好二叉堆，通过将堆顶元素移除（将堆顶元素与最后一个元素交换位置，然后将堆的大小减一）实现堆排序，

这个过程的时间复杂度为

java 实现堆排序

package com.ds.sort;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import static java.util.Collections.swap;

public class MaxHeap<E extends Comparable<E>> {

    private List<E> data;

    private int heapSize;


    public MaxHeap(int capacity) {
        data = new ArrayList<>(capacity);

    }

    public MaxHeap(List<E> data) {
        this.data = data;
        heapSize = data.size();
    }


    public int getHeapSize() {
        return heapSize;
    }

    public void setHeapSize(int heapSize) {
        this.heapSize = heapSize;
    }

    public boolean isEmpty() {
        return data.isEmpty();
    }


    private int parent(int i) {
        if (i <= 0) {
            throw new IllegalArgumentException("no parent");

        }
        return (i - 1) / 2;
    }

    private int left(int i) {
        return 2 * i + 1;
    }

    private int right(int i) {
        return 2 * i + 2;
    }


    /**
     * 二叉树 的left(k)子树和right(k)子树满足堆的性质，但是data[k] 可能小于left(k)或right(k)
     * 将其向下调整，一般也称这个过程为shift down
     *
     * @param k
     */

    private void heapify(int k) {
        int left = left(k);
        int right = right(k);
        int maxIndex = k;
        if (left < heapSize && data.get(left).compareTo(data.get(maxIndex)) > 0) {
            maxIndex = left;
        }
        if (right < heapSize && data.get(right).compareTo(data.get(maxIndex)) > 0) {
            maxIndex = right;
        }
        if (k != maxIndex) {
            swap(data, maxIndex, k);
            heapify(maxIndex);

        }
    }

    /**
     * 使用数组随机构建最小堆的方式为
     * 从最后一个元素的parent开始 到0个元素，依次调用heapify
     */

    public void buildMaxHeap() {
        int lastNodeParent = parent(data.size() - 1);
        for (int i = lastNodeParent; i >= 0; i--) {
            heapify(i);
        }
    }

    /**
     * 通过将堆顶元素移除（将堆顶元素与最后一个元素交换位置，然后将堆的大小减一）实现
     */

    public void heapSort() {
        buildMaxHeap();
        for (int i = heapSize - 1; i > 0; i--) {
            swap(data, 0, heapSize - 1);
            setHeapSize(heapSize - 1);
            heapify(0);
        }

    }

    public static void main(String[] args) {
        List<Integer> data = Arrays.asList(4, 1, 3, 2, 16, 9, 10, 14, 8, 7);
        MaxHeap<Integer> maxHeap = new MaxHeap<>(data);
        maxHeap.heapSort();
        System.out.println(data);
    }


}

github地址

https://github.com/spraysss/data-structure/blob/master/src/main/java/com/ds/sort/MaxHeap.java