深入浅出排序算法(1)-堆排序

内容简介：深入浅出排序算法(1)-堆排序

概述

堆排序 即是利用 堆 这个数据结构来完成 排序 的.所以,要想理解 堆排序 就要先了解 堆 .

堆

堆(Heap) 是一种数据结构,它可以被看做是一棵树的数组对象.一个 二叉堆 拥有以下性质.

• 父节点 k 的左子节点在数组中的索引位置为 2 * k + 1 .

• 父节点 k 的右子节点在数组中的索引位置为 2 * k + 2 .

• 子节点 i 的父节点在数组中的索引位置为 (i - 1) / 2 .

• 父节点 k 的任意子节点都必须小于(或大于) k .

• 根节点必须是最大节点(或最小节点).

最大堆代码实现

public class MaxHeap<T extends Comparable> {

    T[] heap;

    private MaxHeap() {
    }

    public MaxHeap(T[] heap) {
        this.heap = heap;
        buildHeap();
    }

    /**
     * 自底向上构建堆
     */
    private void buildHeap() {
        int length = heap.length;
        // 当堆为空或者长度为1时不需要任何操作
        if (length <= 1)
            return;

        int root = (length - 2) >>> 1; // (i - 1) / 2
        while (root >= 0) {
            heapify(heap, length, root);
            root--;
        }
    }

    /**
     * 调整堆的结构
     *
     * @param heap   堆
     * @param length 堆的长度
     * @param root   根节点索引
     */
    public void heapify(T[] heap, int length, int root) {
        if (root >= length)
            return;

        int largest = root; // 表示root,left,right中最大值的变量
        int left = (root << 1) + 1; // 左子节点,root * 2 + 1
        int right = left + 1; // 右子节点,root * 2 + 2

        // 找出最大值
        if (left < length && greater(heap[left], heap[largest]))
            largest = left;
        if (right < length && greater(heap[right], heap[largest]))
            largest = right;

        // 如果largest发生变化,将largest与root交换
        if (largest != root) {
            T t = heap[root];
            heap[root] = heap[largest];
            heap[largest] = t;
            // 继续向下调整堆
            heapify(heap, length, largest);
        }
    }

    private boolean greater(Comparable a, Comparable b) {
        return a.compareTo(b) > 0;
    }

}

优先队列

普通的队列是基于 先进先出 的,也就是说最先入队的元素永远是在第一位,而 优先队列 中的每一个元素都是拥有 优先级 的, 优先级 最高的元素永远在第一位.

优先队列 也是 贪心算法 的体现,所谓的 贪心算法 即是在问题求解的每一步中总是选择当前最好的结果.

堆 就是用于实现 优先队列 的,因为 堆 的性质与 优先队列 十分吻合.

添加

往 优先队列 中添加元素时,我们只需要将元素添加到数组末尾并调整堆(以下例子均是以最大堆为例).

public boolean add(T t) {
        if (t == null)
            throw new NullPointerException();
        if (size == queue.length)
            resize(queue.length * 2);
        int i = size;
		// 如果当前队列为空,则不需要进行堆调整直接插入元素即可
        if (i == 0)
            queue[0] = t;
        else
            swim(i, t);
        size++;
        return true;
    }
	
	// 上浮调整
    private void swim(int i, T t) {
        Comparable<? super T> key = (Comparable) t;
        while (i > 0) {
            int parent = (i - 1) >>> 1;
            T p = (T) queue[parent];
			// 如果key小于他的父节点(符合最大堆规则)则结束调整
            if (key.compareTo(p) < 0)
                break;
            queue[i] = p;
            i = parent;
        }
        queue[i] = key;
    }

删除

删除操作要稍微麻烦一点,将 优先队列 中末尾的元素放到队头并进行堆调整.

public T poll() {
        if (isEmpty())
            return null;
        int s = --size;
        Object result = queue[0];
        Object end = queue[s];
        queue[s] = null;
        if (s != 0)
            sink(0, (T) end);
        if (size <= queue.length / 4)
            resize(queue.length / 2);
        return (T) result;
    }
	
	// 下沉调整
    private void sink(int i, T t) {
        Comparable<? super T> key = (Comparable<? super T>) t;
        int half = size >>> 1;
        while (i < half) {
            int child = (i << 1) + 1; // 左子节点
            int right = child + 1; // 右子节点
            T max = (T) queue[child];
            // find maximum element
            if (right < size &&
                    ((Comparable<? super T>) max).compareTo((T) queue[right]) < 0)
                max = (T) queue[child = right];
			// key大于它的最大子节点(符合最大堆规则)则结束调整	
            if (key.compareTo(max) > 0)
                break;
            queue[i] = max;
            i = child;
        }
        queue[i] = key;
    }

点击查看优先队列完整代码

堆排序

实现 堆排序 有两种方法,一种是使用 优先队列 ,另一种是直接使用 堆 .

直接使用堆实现堆排序

// 使用最大堆实现堆排序
    private static void maxHeapSort(Comparable[] a) {
        MaxHeap<Comparable> maxHeap = new MaxHeap<>(a);
        //不断地将最大堆中顶端元素(最大值)与最底部的元素(最小值)交换
        for (int i = a.length - 1; i > 0; i--) {
            Comparable largest = a[0];
            a[0] = a[i];
            a[i] = largest;
            // 堆减少,并调整新的堆
            maxHeap.heapify(a, i, 0);
        }
    }

使用优先队列实现堆排序

// 使用优先队列实现堆排序
    private static void pqSort(Comparable[] a) {
        MinPriorityQueue<Comparable> priorityQueue = new MinPriorityQueue<>();
        for (int i = 0; i < a.length; i++) {
            priorityQueue.add(a[i]);
        }
        for (int i = 0; i < a.length; i++) {
            a[i] = priorityQueue.poll();
        }
    }

本文作者为 SylvanasSun(sylvanassun_xtz@163.com) ,转载请务必指明原文链接.

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

• 算法之常见排序算法-冒泡排序、归并排序、快速排序
• 排序算法之冒泡排序改进算法
• 快速排序算法，C语言快速排序算法深入剖析
• 排序算法下——桶排序、计数排序和基数排序
• 数据结构和算法面试题系列—排序算法之快速排序
• 数据结构和算法面试题系列—排序算法之基础排序

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。