【Java】实现堆,并使用堆模拟优先级队列
发布日期:2021-05-11 02:01:13 浏览次数:15 分类:精选文章

本文共 6862 字,大约阅读时间需要 22 分钟。

������������������������������

������������������������������������������������������������������������������������������������������������������������������������������������������������������

���������������������������������������������������������������������������������������������������������������Priority Queue������������������������������������Min-Heap������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������


������������������������������

������������������������������������������������������������������

  • ��������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������� size ��������������������������������������������� capacity��������������������������������������������� 100���

  • ���������������������������������������������������������������������������������������������������������

    • arr���������������������������������
    • size������������������������������������������
  • ���������������shiftDown���������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������

  • ���������������shiftUp���������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������


  • ���������������������

    ������������������������������������������������������

    1. ���������������shiftDown���

    ��������� shiftDown ���������������������������������������������������������������������

    public void shiftDown(int[] arr, int index, int size) {
    int parent = index;
    int child = 2 * parent + 1;
    while (child < size) {
    // ���������������������������������
    if (child + 1 < size && arr[child] > arr[child + 1]) {
    child = child + 1;
    }
    // ������������������������������������
    if (arr[child] < arr[parent]) {
    int tmp = arr[child];
    arr[child] = arr[parent];
    arr[parent] = tmp;
    } else {
    break;
    }
    parent = child;
    child = 2 * parent + 1;
    }
    }

    ��������������������������������������� index ���������������������������������������������������������������������������������������������������������������

    2. ���������������shiftUp���

    shiftUp ������������������������������������������������������������������������������������������������������������������

    public void shiftUp(int[] arr, int size, int index) {
    int child = index;
    int parent = (child - 1) / 2;
    while (child > 0) {
    // ������������������������������������
    if (arr[child] < arr[parent]) {
    int tmp = arr[child];
    arr[child] = arr[parent];
    arr[parent] = tmp;
    } else {
    break;
    }
    child = parent;
    parent = (child - 1) / 2;
    }
    }

    ������������������������������������������ shiftUp ���������������������������������������������������������������������������������������������������������������������������������������


    ������������

    ���������������������������������������������������������������������������������������������

    public class MyPriorityQueue {
    private int[] arr = new int[100];
    private int size = 0;
    @Override
    public String toString() {
    int[] copy = Arrays.copyOf(arr, size);
    return Arrays.toString(copy);
    }
    public void shiftDown(int[] arr, int index, int size) {
    int parent = index;
    int child = 2 * parent + 1;
    while (child < size) {
    if (child + 1 < size && arr[child] > arr[child + 1]) {
    child = child + 1;
    }
    if (arr[child] < arr[parent]) {
    int tmp = arr[child];
    arr[child] = arr[parent];
    arr[parent] = tmp;
    } else {
    break;
    }
    parent = child;
    child = 2 * parent + 1;
    }
    }
    public void shiftUp(int[] arr, int size, int index) {
    int child = index;
    int parent = (child - 1) / 2;
    while (child > 0) {
    if (arr[child] < arr[parent]) {
    int tmp = arr[child];
    arr[child] = arr[parent];
    arr[parent] = tmp;
    } else {
    break;
    }
    child = parent;
    parent = (child - 1) / 2;
    }
    }
    public void creatHeap(int[] newArr) {
    for (int x : newArr) {
    arr[size++] = x;
    }
    for (int i = (size - 1 - 1) / 2; i >= 0; i--) {
    shiftDown(arr, i, size);
    }
    }
    public void creatHeap2(int[] arr) {
    for (int x : arr) {
    offer(x);
    }
    }
    public void offer(int val) {
    if (size >= arr.length) {
    return;
    }
    arr[size++] = val;
    shiftUp(arr, size, size - 1);
    }
    public Integer peek() {
    if (size == 0) {
    return null;
    }
    return arr[0];
    }
    public Integer poll() {
    if (size == 0) {
    return null;
    }
    int res = arr[0];
    int temp = arr[0];
    arr[0] = arr[size - 1];
    arr[size - 1] = temp;
    size--;
    shiftDown(arr, 0, size);
    return res;
    }
    }

    ������������

    ������������������������������������������������������������������������������

    public static void main(String[] args) {
    MyPriorityQueue m = new MyPriorityQueue();
    m.offer(6);
    m.offer(5);
    m.offer(4);
    m.offer(3);
    int[] arr = {9, 2, 7};
    m.creatHeap(arr);
    System.out.println(m.peek()); // ���������������������3
    Integer res = m.poll();
    System.out.println(res); // ���������������������3
    res = m.poll();
    System.out.println(res); // ���������������������4
    }

    ���������������������������������������������������������������������������������������������������������������

    3
    3
    4

    ������

    ���������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������heap��������������������������������������������������������������������������������������������������� Ensureheap property���

    ���������������������������������������������������������������������������������������������������������������������������������������������������

    上一篇:【Java排序】详解七种排序:插入排序、希尔排序、冒泡排序,选择排序,快速排序,堆排序,归并排序
    下一篇:【Java 数据结构】 优先级队列(堆)

    发表评论

    最新留言

    网站不错 人气很旺了 加油
    [***.192.178.218]2025年04月19日 07时52分44秒