堆的原理与实现

2021年9月22日 13点热度 0条评论 来源: funtrin

堆的原理与实现

概述

堆是一种数据结构,它可以保证,无论以何种顺序向堆中添加数,添加多少数,每一次取出来的都是当前堆中最小的数或者最大的数。我们可以把堆想象成一种完全二叉树结构,最小的数或最大的数在根节点的位置上,并且每一个节点都是其对应子树中的最小值或最大值。如下图所示:

一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。

但实际上我们一般使用数组来实现堆,而不是二叉树(二叉树也可以),因为任意节点的索引与它的父子节点的索引之间是有规律的。假设任意节点在数组中的索引为i,那么它的父子节点的索引与它的索引有如下关系:

  • 父节点索引:i/2
  • 左子节点索引:2 * i + 1
  • 右子节点索引:2 * i + 2

如下图所示:

如何实现堆?

插入数据

知道了堆的本质是一个数组,那么如向堆中插入数字?一般的策略是将要插入的数先放到堆的末尾,然后依次与它的的父节点的值比较,如果小于父节点的值就向上替换,直到数字不小于它的父节点的值或者已经没有父节点才停止,如下图所示:

代码

// 向堆中插入元素
public void heapInsert(int num) {
    // 容量不够,对数组进行扩容
    if (size == array.length) {
        array = enlargeArray(array);
    }
    array[size++] = num;
    int index = size - 1;
    while (index > 0) {
        if (array[index] < array[index / 2]) {
            swap(array, index, index / 2);
            index = index / 2;
        } else {
            break;
        }
    }
}

取出最小值

取出最小值很容易实现,直接删除并返回数组中的第一个数就可以了,但为了但为了每一次取出的都是最小值,我们还应该将数组中剩下的数,也调整成一个堆的结构。一般的策略是将堆中最后一个数放到数组的第一个位置,然后和它的左右子节点中最小的值比较,如果小于子节点中的最小值,那就把它和子节点中最小的值交换,循环往复,知道不小于子节点中的值,或是已经到最后一层才停止。如下图所示:

代码

// 返回并删除最小元素
public int pop() {
    int temp = array[0];
    array[0] = array[--size];
    int index = 0;
    int left = 1;
    while (left < size) {
        int min = 0;
        if (left + 1 < size) {
            min = array[left] < array[left + 1] ? left : left + 1;
        } else {
            min = left;
        }
        if (array[index] > array[min]) {
            swap(array, min, index);
            index = min;
            left = index * 2 + 1;
        } else {
            break;
        }
    }
    return temp;
}

完整代码

每个人的具体实现不同,代码仅供参考。

public class Heap {
    // 初始容量为8
    private int[] array = new int[8];
    private int size = 0;

    public Heap() {
    }

    // 向堆中插入元素
    public void heapInsert(int num) {
        if (size == array.length) {
            array = enlargeArray(array);
        }
        array[size++] = num;
        int index = size - 1;
        while (index > 0) {
            if (array[index] < array[index / 2]) {
                swap(array, index, index / 2);
                index = index / 2;
            } else {
                break;
            }
        }
    }

    // 返回并删除最小元素
    public int pop() {
        int temp = array[0];
        array[0] = array[--size];
        int index = 0;
        int left = 1;
        while (left < size) {
            int min = 0;
            if (left + 1 < size) {
                min = array[left] < array[left + 1] ? left : left + 1;
            } else {
                min = left;
            }
            if (array[index] > array[min]) {
                swap(array, min, index);
                index = min;
                left = index * 2 + 1;
            } else {
                break;
            }
        }
        return temp;
    }


    // 交换数组中两个不同索引上的值
    private void swap(int[] array, int i, int j) {
        array[i] = array[i] ^ array[j];
        array[j] = array[j] ^ array[i];
        array[i] = array[i] ^ array[j];
    }

    // 扩容数组
    private int[] enlargeArray(int[] array) {
        return Arrays.copyOf(array, array.length * 2);
    }
}
    原文作者:funtrin
    原文地址: https://www.cnblogs.com/funtirn/p/15317949.html
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。