手写大根堆

package com.harrison.class04;
public class Code01_MaxHeap {
  public static class MyMaxHeap {
    private int[] heap;
    private final int limit;
    private int heapSize;
    public MyMaxHeap(int limit) {
      heap = new int[limit];
      heapSize = 0;
      this.limit = limit;
    }
    public void push(int value) {
      if (heapSize == limit) {
        throw new RuntimeException("heap is full");
      }
      heap[heapSize] = value;
      heapInsert(heap, heapSize++);
    }
    // 堆结构的两个关键操作：从某个位置开始往上看
    // 动态地建立大根堆
    // 如果收了N个数，时间复杂度为logN
    public static void heapInsert(int[] arr, int index) {
      while (arr[index] > arr[(index - 1) / 2]) {
        swap(arr, index, (index - 1) / 2);
        index = (index - 1) / 2;
      }
    }
    // 返回最大值，并在大根堆中把最大值删掉
    // 剩下的数，依然保持大根堆组织
    public int pop() {
      int ans = heap[0];
      swap(heap, 0, --heapSize);
      heapify(heap, 0, heapSize);
      return ans;
    }
    // 堆结构的两个关键操作：从某个位置开始往下调,时间复杂度logN
    // heapSize 自己想象范围的大小，并不是数组的实际大小！！！
    public static void heapify(int[] arr, int index, int heapSize) {
      int left=(2*index)+1;
      while(left<heapSize) {
        int largest=(left+1<heapSize && arr[left+1]>arr[left])?left+1:left;
        int allLargest=arr[largest]>arr[index]?largest:index;
        if(allLargest==index) {
          break;
        }
        swap(arr, allLargest, index);
        index=allLargest;
        left=(2*index)+1;
      }
    }
    public boolean isEmpty() {
      return heapSize==0;
    }
    public boolean isFull() {
      return heapSize==limit;
    }
  }
  public static void swap(int[] arr, int i, int j) {
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
  }
  public static class RightMaxHeap{
    private int[] arr;
    private int size;
    private final int limit;
    public RightMaxHeap(int limit) {
      this.limit=limit;
      arr=new int[limit];
      size=0;
    }
    public void push(int value) {
      if(size==limit) {
        throw new RuntimeException("heap is full");
      }
      arr[size++]=value;
    }
    public int pop() {
      int maxIndex=0;
      for(int i=1; i<size; i++) {
        if(arr[maxIndex]<arr[i]) {
          maxIndex=i;
        }
      }
      int ans=arr[maxIndex];
      arr[maxIndex]=arr[--size];
      return ans;
    }
    public boolean isEmpty() {
      return size==0;
    }
    public boolean isFull() {
      return size==limit;
    }
  }
  public static void main(String[] args) {
    int testTimes=1000000;
    int limit=1000;
    int value=100;
    System.out.println("test begin");
    for(int i=0; i<testTimes; i++) {
      // [1,1000],防止出现零，否则一开始堆的大小就为0
      int curLimit=(int)(Math.random()*limit)+1;
      MyMaxHeap my=new MyMaxHeap(curLimit);
      RightMaxHeap test=new RightMaxHeap(curLimit);
      int curOopsTimes=(int)(Math.random()*limit);
      for(int j=0; j<curOopsTimes; j++) {
        if(my.isEmpty()!=test.isEmpty()) {
          System.out.println("Oops");
        }
        if(my.isFull()!=test.isFull()) {
          System.out.println("Oops");
        }
        if(my.isEmpty()) {
          int curValue=(int)(Math.random()*(value+1));
          my.push(curValue);
          test.push(curValue);
        }else if(my.isFull()) {
          if(my.pop()!=test.pop()) {
            System.out.println("Oops");
          }
        }else {
          if(Math.random()<0.5) {
            int curValue=(int)(Math.random()*(value+1));
            my.push(curValue);
            test.push(curValue);
          }else {
            if(my.pop()!=test.pop()) {
              System.out.println("Oops");
            }
          }
        }
      }
    }
    System.out.println("finish");
  }
}