算法-----堆结构实现优先级队列

时间:2022-07-31 10:13:37
  • package com.eshore.sweetop.dataframe;
  • import java.util.Arrays;
  • public class MaxHeapQeuen {
  •     private static int parent(int i) {
  •         return (i - 1) >> 1;
  •     }
  •     private static int left(int i) {
  •         return i << 1 | 1;
  •     }
  •     private static int right(int i) {
  •         return (i + 1) << 1;
  •     }
  •     private static void maxHeapify(int[] a, int i, int size) {
  •         int l = left(i);
  •         int r = right(i);
  •         int largest = -1;
  •         if (l < size && a[l] > a[i]) {
  •             largest = l;
  •         } else {
  •             largest = i;
  •         }
  •         if (r < size && a[r] > a[largest]) {
  •             largest = r;
  •         }
  •         if (largest != i) {
  •             a[i] ^= a[largest];
  •             a[largest] ^= a[i];
  •             a[i] ^= a[largest];
  •             maxHeapify(a, largest, size);
  •         }
  •     }
  •     public static void buildMaxHeap(int[] a) {
  •         for (int i = a.length / 2 - 1; i > -1; i--) {
  •             maxHeapify(a, i, a.length);
  •         }
  •     }
  •     private static int max(int[] a) {
  •         return a[0];
  •     }
  •     // 这里其实是不够的,a.length应该换成一个全局变量,逐一递减,留给大家写
  •     private static int exmax(int[] a) {
  •         int max = a[0];
  •         a[0] = a[a.length - 1];
  •         maxHeapify(a, 0, a.length - 1);
  •         return max;
  •     }
  •     private static void set(int[] a, int i, int value) {
  •         if (value < a[i]) {
  •             throw new RuntimeException(
  •                     "new value is smaller than current value ");
  •         }
  •         a[i] = value;
  •         while (i > 0 && a[parent(i)] < a[i]) {
  •             a[i] ^= a[parent(i)];
  •             a[parent(i)] ^= a[i];
  •             a[i] ^= a[parent(i)];
  •             i = parent(i);
  •         }
  •     }
  •     private static int[] incream(int[] a) {
  •         int[] b = new int[a.length + 1];
  •         for (int i = 0; i < a.length; i++) {
  •             b[i] = a[i];
  •         }
  •         return b;
  •     }
  •     private static void add(int[] a, int value) {
  •         a[a.length-1] = Integer.MIN_VALUE;
  •         set(a, a.length - 1, value);
  •     }
  •     public static void main(String[] args) {
  •         int[] a = { 2361147129513 };
  •         buildMaxHeap(a);
  •         a = incream(a);
  •         add(a, 14);
  •         System.out.println(max(a));
  •     }
  • }