04月14, 2018

MaxHeap结构及排序算法

本文总结了MaxHeap数据结构的概念以及在此基础上的排序算法HeapSort。

BinaryHeap-二叉堆

BinaryHeap基于一个数据结构概念:完全二叉树

  • 二叉树:子节点都小于父节点的树形结构。

  • 完全二叉树

    • 除了最后一层节点之外,其他层的节点个数必须是最大数,比如:第一层1个节点 第二层2^1个节点 ,第三层2^2个节点...N层2^n-1个节点。
    • 最后一层节点必须都集中在树的左侧。

BinaryHeap-堆就是一棵完全二叉树,树顶元素总是最大也叫最大堆alt

数组实现最大堆:自上而下,自左至右依序添加角标,那么很容易发现父子节点的规律:父节点角标N的左子节点角标是2N,右子节点角标是2N+1。反之子节点角标/2即父节点角标。

结构实现

容器:
@Slf4j
public class MaxHeap<T extends Comparable> {
    // 元素集合
    private T[] data;

    // 容器元素个数
    private int count;

    // 容器大小
    private int capacity;

    // 根据元素数量构造容器
    public MaxHeap(int capacity) {
        this.data = (T[]) new Comparable[capacity + 1];
        this.count = 0;
        this.capacity = capacity;
    }
}
新增元素(ShiftUp)

新增元素基于Heap结构中ShiftUp的操作。所谓ShiftUp是描述从堆尾部增加新元素并向上比较替换直至满足完全二叉树特性的过程。 如:新增元素4在arrs[10]位置上。 Alt text 依次向上比较父节点arrs[5],arrs[2],最终交换在arrs[2]的位置。

alt

// 最大堆用shif-up方式排序
private void shiftUp(int i) {
    while (i > 1 && data[i / 2].compareTo(data[i]) < 0) {
        // 父节点小于子节点
        commonUtils.swap(data, i / 2, i);
        // 下一个父节点
        i /= 2;
    }

}

新增元素时默认在数组尾部,新元素结构需要保持最大堆的性质,所以新元素要与父节点比较并交换(大于父节点的情况下),直到存在于一个大于新元素的父节点下。这个过程被称为堆的ShiftUp

删除元素(ShiftDown)

对应ShiftUp操作,ShiftDown从堆中取出根节点元素。此时堆中最后一个元素需要替换到根节点处,堆count -= 1,依然维持完全二叉树的性质。根节点元素再依次向下比较替换的过程。

  • 取出根节点即Heap的最大值,并将尾节点元素替换至根节点处;

alt

  • 从根节点开始向下与左右子节点中较大的节点比较交换,直到底层尾节点;

alt 至此Heap在删除根元素后,通过ShifDown操作后,完成新MaxHeap平衡二叉树的特性。

代码实现:

   // shiftDown操作,将头结点移动至树合适的位置
    private void shiftDown(int i){
        // 还有子节点的情况:MaxHeap还存在左子节点
        while (2 * i <= count){
            // 待交换节点:初始化为左节点
            int j = 2 * i;
            // 存在右节点 && 右节点 > 左节点
            if(j + 1 <= count && data[j+1].compareTo(data[j]) > 0){
                // 取右节点
                j += 1;
            }

            // 子节点小于等于父节点 符合最大堆特性
            if(data[j].compareTo(data[i]) <= 0){
                break;
            }
            commonUtils.swap(data,i,j);
            i = j;
        }
    }

Heapify

  • 将一个数组按顺序映射成一个从上至下从左至右排序的MaxHeap过程即是Heapify。
  • 叶子节点:没有子节点的节点.
  • 对于一个完全二叉树来说,最后一个元素节点角标/2 是最后一个非叶子节点的角标

Heapify从最后一个非叶子节点开始做ShiftDown操作:

         // Heapify
        // 最后一个非叶子节点: n/2
        for (int i = n/2; i >= 1 ; i--) {
            shiftDown(i);
        }

HeapSort(O(NlogN))

HeapSort是对数组做Heapify的基础上的排序操作。已知对于一个MaxHeap结构根节点都为最大值,所以可以循环操作对数组排序:拿取根节点 => ShiftDown。

public void sort(Comparable[] arrs) {
    int n = arrs.length;
    MaxHeap<Comparable> heap = new MaxHeap<>(arrs);
    // 利用MaxHeap的extracMax()依次获取最大值,倒置进数组
    for (int i = n - 1; i >= 0; i--) {
        arrs[i] = heap.extractMax();
    }
}

Max-Heap构造:

/**
 * Heap-Sort
 * @param arrs
 */
public MaxHeap(T[] arrs){


    int n = arrs.length;
    data = (T[])new Comparable[n + 1];
    capacity = n;

    for (int i = 0; i < n; i++) {
        // Max-Heap从1开始
        data[i + 1] = arrs[i];
    }
    count = n;

    // Heapify
    // 最后一个非叶子节点: n/2
    for (int i = n/2; i >= 1 ; i--) {
        shiftDown(i);
    }

}

HeapSort优化

但是该种办法需要开辟n个内存空间的MaxHeap且在利用ShiftDown排序时,需要进行swap()操作。所以可以利用Heapify进行数组原地的排序并参照InsertionSort的优化思路利用Index的交换减少swap()。

alt

  • 将MaxHeap[0] = e (根节点)与 MaxHeap[n] = v(尾节点)swap(),此时n为正确排序位置。
  • 此时MaxHeap[0 ... n -1]不是MaxHeap,故对e做ShiftDown操作完成Heapify。
  • 循环执行上述步骤直到数组从尾到头的遍历。

原地HeapSort:

public void sort(Comparable[] arrs) {
    int n = arrs.length;
    // 通过heapify将数组构成一个完全二叉树
    // arrs[index]从0开始,二叉树最后一个叶子节点的父节点Index为(count - 1)/2
    for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
        shiftDown(arrs, n, i);
    }

    // MaxHeap的头节点元素是数组最大值,遍历取出头节点放到尾部,再做Heapify重复该动作,
    for (int i = n - 1; i >= 0; i--) {
        // 将头节点(最大值)放到数组尾部
        commonUtils.swap(arrs, 0, i);
        // 剩余部分做heapify
        shiftDown(arrs,i,0);
    }

}

alt 由图可推断,MaxHeap从数组0开始排序后:

  • parent(i) = (i - 1) / 2
  • left child(i) = (2 * i) + 1
  • right child(i) = (2 * i) + 2

swap优化:

  private void shiftDown(Comparable[] arrs, int n, int i) {
        // 待shiftDown元素
        Comparable e = arrs[i];

        // 存在子节点
        while (2 * i + 1 < n) {
            // 左子节点
            int j = 2 * i + 1;
            // 存在子右节点 且 右节点 > 左节点 取右节点
            if (j + 1 < n && arrs[j + 1].compareTo(arrs[j]) > 0) {
                j += 1;
            }

            // 待shiftDown元素 > 子节点 => 不需要shiftDown
            if (e.compareTo(arrs[j]) >= 0) {
                break;
            }

            arrs[i] = arrs[j];
            i = j;
        }
        // 只做一次交换
        arrs[i] = e;
    }

排序性能测试

在对30000条随机元素的排序结果:

[main] 2018-04-14 01:03:29:083 - ====================== Method Start ======================== [main] 2018-04-14 01:03:29:083 - ---- Arrays Size ---- : [30000] [main] 2018-04-14 01:03:29:099 - ---- Profiling Result ---- : Spend [16ms] on [net.check321.algorithms.sorting.advanced.HeapSort] [main] 2018-04-14 01:03:29:099 - ---- Verify Result ---- : [true] [main] 2018-04-14 01:03:29:099 - ====================== Method Start ======================== [main] 2018-04-14 01:03:29:099 - ---- Arrays Size ---- : [30000] [main] 2018-04-14 01:03:29:113 - ---- Profiling Result ---- : Spend [14ms] on [net.check321.algorithms.sorting.advanced.HeapSortWithArray] [main] 2018-04-14 01:03:29:113 - ---- Verify Result ---- : [true]


alt

本文链接:https://check321.net/post/max_heap.html

-- EOF --

Comments

请在后台配置评论类型和相关的值。