堆排序HeapSort

作者: spraysss | 来源:发表于2020-01-22 14:44 被阅读0次

python实现堆排序(HeapSort)
堆排序HeapSort
堆排序（HeapSort）
HeapSort堆排序
算法分析与设计复习
HeapSort堆排序详解
数组-堆排序
堆排序算法
排序算法之5：堆排序 HeapSort
堆排序

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

Like merge sort,but unlike insertion sort, heapsort’s running time is $O(nlogn)$ . 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

堆排序是一种原地排序
堆排序的时间复杂度为 $O(nlogn)$
堆排序是一种不稳定的排序

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

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

堆排序可使用数组实现的完全二叉树结构，对数组索引为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的时间复杂度为 $O(h)$

buildMaxHeap

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

heapSort

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

这个过程的时间复杂度为 $O(nlgn)$

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);
    }


}