최대 힙 (Max Heap)

Main.java

/**
 * 최대 힙 (Max Heap)
 * 
 * @author devetude
 */
public class Main {
	/**
	 * 메인 메소드
	 * 
	 * @param args
	 */
	public static void main(String args[]) {
		// 최대 힙 객체 생성
		MaxHeap maxHeap = new MaxHeap();

		// 데이터 추가 및 출력
		maxHeap.offer(1);
		maxHeap.offer(2);
		maxHeap.offer(3);
		maxHeap.offer(4);
		maxHeap.offer(5);
		System.out.println(maxHeap.toString());

		// 데이터 삭제 및 출력
		System.out.println(maxHeap.toString());
		System.out.println(maxHeap.poll());
		System.out.println(maxHeap.toString());
		System.out.println(maxHeap.poll());
		System.out.println(maxHeap.toString());
		System.out.println(maxHeap.poll());
		System.out.println(maxHeap.toString());
	}

	/**
	 * 최대 힙 이너 클래스
	 * 
	 * @author devetude
	 */
	private static class MaxHeap {
		// 힙 최대 크기 상수
		private static final int MAX_HEAP_SIZE = 1000;

		// 힙 배열 변수
		private int[] heap;

		// 힙 크기 변수
		private int size;

		/**
		 * 생성자
		 */
		public MaxHeap() {
			heap = new int[MAX_HEAP_SIZE];
			size = 0;
		}

		/**
		 * 두 인덱스에 해당하는 힙 값을 변경하는 메소드
		 * 
		 * @param aIdx
		 * @param bIdx
		 */
		public void swapHeap(int aIdx, int bIdx) {
			int tmpData = heap[aIdx];
			heap[aIdx] = heap[bIdx];
			heap[bIdx] = tmpData;
		}

		/**
		 * 힙에 데이터를 추가하는 메소드
		 * 
		 * @param data
		 */
		public void offer(int data) {
			int offerIdx = ++size;
			heap[offerIdx] = data;

			while (offerIdx > 1) {
				int rootIdx = offerIdx / 2;

				if (heap[rootIdx] < heap[offerIdx]) {
					swapHeap(rootIdx, offerIdx);

					int tmpIdx = offerIdx;
					offerIdx = rootIdx;
					rootIdx = tmpIdx;
				}

				else {
					break;
				}
			}
		}

		/**
		 * 힙에 데이터를 가져오는 메소드
		 * 
		 * @return
		 */
		public int poll() {
			int rootIdx = 1;
			int pollData = heap[rootIdx];

			heap[rootIdx] = heap[size];
			heap[size--] = Integer.MIN_VALUE;

			while (true) {
				int leftIdx = rootIdx * 2;
				int rightIdx = rootIdx * 2 + 1;

				if (heap[rootIdx] >= heap[leftIdx] && heap[rootIdx] >= heap[rightIdx]) {
					break;
				}

				else if (heap[leftIdx] > heap[rightIdx]) {
					swapHeap(rootIdx, leftIdx);
					rootIdx = leftIdx;
				}

				else {
					swapHeap(rootIdx, rightIdx);
					rootIdx = rightIdx;
				}
			}

			return pollData;
		}

		/**
		 * 힙의 내용을 문자열로 만들어주는 메소드
		 * 
		 * @return
		 */
		public String toString() {
			StringBuilder sb = new StringBuilder();
			sb.append("[");

			if (size > 0) {
				sb.append(" ");
			}

			for (int i = 1; i < size; i++) {
				sb.append(heap[i]).append(", ");
			}

			if (size > 0) {
				sb.append(heap[size]).append(" ");
			}

			return sb.append("]").toString();
		}
	}
}