heapsort

基础知识

• 普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。
  在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。

• 堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：
  1、堆中某个节点的值总是不大于或不小于其父节点的值；
  2、堆总是一棵完全二叉树。

用堆来实现优先队列

最大元素在根节点

/**
 * Description: 基于堆的优先队列
 * Author: Hodge
 * Date: 2018-03-28
 */
public class MaxPQ<Key extends Comparable<Key>>
{
    private Key[] pq;   //基于堆的完全二叉树
    private int N = 0;

    public MaxPQ(int manN)
    {
        pq = (Key[]) new Comparable[manN + 1];
    }

    public boolean isEmpty()
    {
        return N == 0;
    }

    public int size()
    {
        return N;
    }

    public void insert(Key v)
    {
        pq[++N] = v;
        swim(N);
    }

    public Key delMax()
    {
        Key max = pq[1];    //根节点为最大元素
        exch(1, N--);     //交换
        pq[N + 1] = null;   //防止对象游离
        sink(1);        //恢复堆的有序性
        return max;
    }

    private void sink(int k)
    {
        while (2 * k <= N)
        {
            int j = 2 * k;
            if (j < N && less(j, j + 1))
            {
                j++;
            }
            exch(k, j);
            k = j;
        }
    }

    private void swim(int k)
    {
        while (k > 1 && less(k / 2, k))
        {
            exch(k / 2, k);
            k /= 2;
        }
    }

    private boolean less(int i, int j) //比较两个元素大小
    {
        return pq[i].compareTo(pq[j]) < 0;
    }

    private void exch(int i, int j) //交换两个元素位置
    {
        Key t = pq[i];
        pq[i] = pq[j];
        pq[j] = t;
    }
}

堆排序

将所有元素插入一个查找最小（或最大）元素的优先队列，通过重复调用删除最小元素的操作排序

堆的构造

最傻方法：从左到右遍历数组，逐一使用swim()方法，复杂度NlogN
优化：从N/2到1节点逐一使用sink()方法递归建立起堆的秩序

代码

import edu.princeton.cs.algs4.StdOut;

import java.util.Scanner;

/**
 * Description: 堆排序
 * Author: Hodge
 * Date: 2018-03-28
 */
public class HeapSort
{
    private HeapSort()
    {
    }

    public static void sort(Comparable[] pq)
    {
        int n = pq.length;
        for (int k = n / 2; k >= 1; k--)    //构造堆
            sink(pq, k, n);
        while (n > 1)           //逐一取值
        {
            exch(pq, 1, n--);
            sink(pq, 1, n);
        }
    }

    private static void exch(Object[] pq, int i, int j)
    {
        Object swap = pq[i - 1];
        pq[i - 1] = pq[j - 1];
        pq[j - 1] = swap;
    }

    private static void sink(Comparable[] pq, int k, int n)
    {
        while (2 * k <= n)
        {
            int j = 2 * k;
            if (j < n && less(pq, j, j + 1))
            {
                j++;
            }
            if (!less(pq, k, j))
            {
                break;
            }
            exch(pq, k, j);
            k = j;
        }
    }

    private static boolean less(Comparable[] pq, int i, int j)
    {
        return pq[i - 1].compareTo(pq[j - 1]) < 0;
    }

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        String arr[] = input.split(" ");
        Comparable[] num = new Comparable[arr.length];
        for (int i = 0; i < arr.length; i++)
        {
            num[i] = Integer.parseInt(arr[i]);
        }
        HeapSort.sort(num);
        show(num);

    }

    private static void show(Comparable[] a) //打印数组
    {
        for (Comparable anA : a)
        {
            StdOut.print(anA + " ");
        }
        StdOut.println();
    }
}

分析

将N个元素排序，堆排序只需要少于(2NlgN+2N)次比较以及一半次数的交换