原创

优先队列-二叉堆-堆排序原理-Java相关API

完全二叉树概念

  • 除了最后一层,前面所有层都是满的
  • 最后一层是从左到右
  • 是一个二叉树

  • 满足完全二叉树
  • 父节点存储的元素比子节点大

上浮

  • 不符合堆规则的节点,与父节点交换
  • 直到上浮到符合为止

下沉

  • 不符合规则的点,与子节点中较大的交换
  • 直到符合为止

入队

  • 待插入元素放到堆的最后面
  • 然后上浮至合适位置
  • 时间复杂度O(log N)

出队

  • 根元素取出,最后一个元素切换到根元素位置
  • 然后将其下沉至合适为止
  • 时间复杂度O(log N)

这就是出队的代码,build_heap以及heapify以及swap均在下面可以看到

    private void heap_sort(int[] tree, int n) {
        build_heap(tree, n);
        for (int i = n - 1; i >= 0; i--) {
           swap(tree, i, 0);
           heapify(tree, i, 0);
        }
    }

堆的数据结构

堆可以用一维数组来表示
其父子下标关系为:
i为子,其父的下标为:(i - 1) / 2 此处为取整

p为父:其子下标,左子为: p 2 + 1,右子为:p 2 + 2

heapify操作

对一个二叉树的一个节点及其子节点进行堆化操作
代码如下

    private void heapify(int tree[], int n, int i) {
        if (i >= n) {
            return;
        }
        int c1 = 2 * i + 1;
        int c2 = 2 * i + 2;
        int max = i;
        if (c1 < n && tree[c1] > tree[max]) {
            max = c1;
        }
        if (c2 < n && tree[c2] > tree[max]) {
            max = c2;
        }
        if (max != i) {
            swap(tree, max, i);
            heapify(tree, n, max);
        }
    }

    private void swap(int[] tree, int max, int i) {
        int temp = tree[max];
        tree[max] = tree[i];
        tree[i] = temp;
    }

从下往上heapify,从最后一个节点的父节点开始,从右到左依次heapify

    private void build_heap(int[] tree, int n) {
        int last_node = n - 1;
        int parent = (last_node - 1) / 2;
        for (int i = parent; i >= 0; i--) {
            heapify(tree, n, i);
        }
    }

Java的API

import java.util.PriorityQueue;
优先队列,使用堆实现的

该实现与上面介绍不同,该实现是小顶堆,也就是小的在上面

如何改成大顶堆呢?

方式一:利用Comparator

        PriorityQueue<Integer>priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });

方式二:可以将值设置为负数,取出来的时候取反(取巧方式)

关键API

入队
offer(e)

出队
poll()

获取堆顶元素(不取出)
peek()

正文到此结束
本文目录