手写大根堆

用数组实现一个大根堆

实现功能

• 每给一个数加进数组后，自动调整为大根堆结构（heapInsert()方法）
• 返回大根堆中的最大值，并且在大根堆中把最大值删除，且剩下的数，依然保持为大根堆结构（heapify()方法）

自己手写一个大根堆结构 VS 纯暴力的方法，用对数器测试100万组！！！

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");
	}
}