当前位置:首页>Java>Java 高级教程>Java堆 数据结构和算法

Java堆 数据结构和算法

作者:githubofrico发布时间:2019-09-14 20:58:37地址:https://dwz.cn/AMenD9kw

堆的概念

什么是堆

堆就是用数组实现的二叉树,所有它没有使用父指针或者子指针。堆根据“堆属性”来排序,“堆属性”决定了树中节点的位置。

堆的常用方法

  • 构建优先队列

  • 支持堆排序

  • 快速找出一个集合中的最小值(或者最大值)

Java堆的实现

堆(数组实现)的数据结构及其相关算法:

堆结构实际上是一个完全二叉树,能方便地从中取出最小/大元素,其包含两个要素,即存储数组heap[]和堆大小size。

Java堆的实现为最小堆,具体操作包括:

  • 堆的构建(创建一个空堆,基于数组的构建)

  • 堆的插入(插入到堆尾,再自下向上调整为最小堆)

  • 堆的删除(删除堆顶元素并用堆尾元素添补,再自上向下调整为最小堆)

  • 堆排序(时间复杂度:O(nlgn),空间复杂度O(1),不稳定):升序排序一般用最大堆,不断地将堆顶元素放到数组,最后并缩小堆的范围

  • 堆的打印(树的前序遍历的应用)

创建MinHeap

核心数据结构如下

public class MinHeap {

    private int[] heap;  // 将所有元素以完全二叉树的形式存入数组
    private int size;  // 堆中元素的个数

    /**
     * 构造函数
     * 
     * @description 构建一个大小为size的最小堆
     * @param size
     */
    public MinHeap(int maxSize) {
        heap = new int[maxSize];
    }

    /**
     * 构造函数
     * 
     * @description 基于数组构造最小堆
     * @param arr
     */
    public MinHeap(int[] arr, int maxSize) {
        heap = new int[maxSize > arr.length ? maxSize : arr.length];
        System.arraycopy(arr, 0, heap, 0, arr.length);
        size = arr.length;

        int pos = (size - 2) / 2; // 最初调整位置:最后的分支节点(最后叶节点的父亲)
        while (pos >= 0) {    //依次调整每个分支节点
            shiftDown(pos, size - 1);
            pos--;
        }
    }
}

自上向下调整为最小堆

从不是最小堆调整为最小堆,调整的前提是其左子树与右子树均为最小堆

/**
 * @param start
 * @param end
 */
private void shiftDown(int start, int end) {
    int i = start;       // 起始调整位置,分支节点
    int j = 2 * start + 1;  // 该分支节点的子节点
    int temp = heap[i];   
    while (j <= end) {  // 迭代条件:子节点不能超出end(范围)
        if (j < end) { 
            j = heap[j] > heap[j + 1] ? j + 1 : j; // 选择两孩子中较小的那个
        }
        if (temp < heap[j]) {   // 较小的孩子大于父亲,不做任何处理
            break;
        } else {    // 否则,替换父节点的值
            heap[i] = heap[j];  
            i = j;
            j = 2 * j + 1;
        }
    }
    heap[i] = temp;  // 一步到位
}

自下向上调整为最小堆

原来已是最小堆,添加元素后,确保其还是最小堆

/**     
 * @param start     
 */
private void shiftUp(int start) {
    int j = start;
    int i = (j - 1) / 2;   // 起始调整位置,分支节点
    int temp = heap[j];
    while (j > 0) {      // 迭代条件:子节点必须不为根
        if (temp >= heap[i]) {  //原已是最小堆,所以只需比较这个子女与父亲的关系即可
            break;
        } else {
            heap[j] = heap[i];
            j = i;
            i = (j - 1) / 2;
        }
    }
    heap[j] = temp;   // 一步到位
}

向最小堆插入元素

总是插入到最小堆的最后

/**
 * @param data
 */
public void insert(int data){
    if (size < heap.length) {
        heap[size++] = data;   // 插入堆尾
        shiftUp(size-1);   // 自下而上调整
    }
}

删除堆顶元素

以堆的最后一个元素填充

public void remove() {
    if (size > 0) {
        heap[0] = heap[size-1];   // 删除堆顶元素,并将堆尾元素回填到堆顶
        size --;                  // 堆大小减一
        shiftDown(0, size-1);     // 自上向下调整为最小堆
    }
}

堆排序

每次将最小元素交换到最后

public void sort(){
    for (int i = size - 1; i >= 0; i--) {
        int temp = heap[0];
        heap[0] = heap[i];
        heap[i] = temp;

        shiftDown(0, i-1);
    }

    for (int i = size-1; i >= 0; i--) {
        System.out.print(heap[i] + " ");
    }
}

打印根为 i 的最小堆

/**
 * @param i
 */
public void printMinHeap(int i) {
    if (size > i) {
        System.out.print(heap[i]);
        if (2 * i + 1 < size || 2 * i + 2 < size) {
            System.out.print("(");
            printMinHeap(2 * i + 1);
            System.out.print(",");
            printMinHeap(2 * i + 2);
            System.out.print(")");
        }
    }
}

Java堆测试代码

public class MinHeapTest {
    public static void main(String[] args) {

        int[] arr = {53, 17, 78, 9, 45, 65, 87, 23};
        MinHeap heap = new MinHeap(arr,20);
        System.out.println("堆:");
        heap.printMinHeap(0);
        System.out.println("\n---------------------------\n");
        System.out.println("向堆中插入元素7后,堆变为:");
        heap.insert(7);
        heap.printMinHeap(0);
        System.out.println("\n---------------------------\n");
        System.out.println("删除堆中末尾元素,堆变为:");
        heap.remove();
        heap.printMinHeap(0);
        System.out.println("\n---------------------------\n");
        System.out.println("堆排序结果为:");
        heap.sort();
    }
}