최대 힙 최소 힙

최대 힙은 부모노드가 항상 자식노드보다 크면서 완전 이진트리에 가까운 이진트리를 말합니다. 

최소 힙은 반대로 부모노드가 항상 자식노드보다 작은경우를 말합니다.

최소 힙, 최대 힙은 힙정렬이나 우선순위 큐 에서 사용됩니다.
  

import java.util.Arrays;

public class MinHeap> {
	private T[] heap = null;
	private int size = 0;

	@SuppressWarnings("unchecked")
	public MinHeap() {
		heap = (T[]) new Comparable[1024];
	}

	public boolean isEmpty() {
		return size == 0;
	}

	public void insert(T element) {
		if (size >= heap.length) {
			T[] temp = Arrays.copyOf(heap, heap.length * 2);
			heap = temp;
		}
		heap[size] = element;
		int i = size;
		int p = getParent(i);
		while (p >= 0 && heap[p].compareTo(heap[i]) > 0) {
			T temp = heap[i];
			heap[i] = heap[p];
			heap[p] = temp;
			i = p;
			p = getParent(p);
		}
		size++;
	}

	public T getMinimun() {
		return heap[0];
	}

	public T ExtractMin() {
		T min = heap[0];
		size--;
		heap[0] = heap[size];
		heapify(0);
		return min;
	}

	private void heapify(int i) {
		if (!hasChild(i))
			return;
		int k = getMinimumChild(i);
		if (heap[i].compareTo(heap[k]) > 0) {
			T temp = heap[i];
			heap[i] = heap[k];
			heap[k] = temp;
			heapify(k);
		}

	}

	private boolean hasChild(int i) {
		return (i * 2 + 1) < size;
	}

	private int getParent(int i) {
		return (i - 1) / 2;
	}

	private int getMinimumChild(int i) {
		if ((i * 2 + 2) < size) {
			return heap[i * 2 + 1].compareTo(heap[i * 2 + 2]) < 0 ? i * 2 + 1
					: i * 2 + 2;
		} else if (i * 2 + 1 < size) {
			return i * 2 + 1;
		} else {
			return -1;
		}
	}

	public String toString() {
		String str = "";
		for (int i = 0; i < size; i++) {
			str += i + " : " + heap[i] + "\n";
		}
		return str;
	}

	public static void main(String[] args) {

		/*
		 * MinHeap h = new MinHeap();
		 * java.util.Random rand = new
		 * java.util.Random();
		 * int a[] = new int[20];
		 * for (int i = 0; i < 20; i++) {
		 * a[i] = rand.nextInt(100);
		 * h.insert(a[i]);
		 * }
		 * Arrays.sort(a);
		 * while(!h.isEmpty())
		 * {
		 * System.out.print(h.ExtractMin()+" ");
		 * }
		 * System.out.println();
		 * for(int i:a)
		 * {
		 * System.out.print(i+" ");
		 * }
		 */
	}
}

 

import java.util.Arrays;
  
public class MaxHeap> {
	private T[] heap = null;
	private int size = 0;

	@SuppressWarnings("unchecked")
	public MaxHeap() {
		heap = (T[]) new Comparable[1024];
	}

	public void insert(T element) {
		if (size >= heap.length) {
			T[] temp = Arrays.copyOf(heap, heap.length * 2);
			heap = temp;
		}
		heap[size] = element;
		int i = size;
		int p = getParent(i);
		while (p >= 0 && heap[p].compareTo(heap[i]) < 0) {
			T temp = heap[i];
			heap[i] = heap[p];
			heap[p] = temp;
			i = p;
			p = getParent(p);
		}
		size++;
	}

	public T getMaximun() {
		return heap[0];
	}

	public T ExtractMax() {
		T max = heap[0];
		size--;
		heap[0] = heap[size];
		heapify(0);
		return max;
	}

	private void heapify(int i) {
		if (!hasChild(i))
			return;
		int k = getMaximumChild(i);
		if (heap[i].compareTo(heap[k]) < 0) {
			T temp = heap[i];
			heap[i] = heap[k];
			heap[k] = temp;
			heapify(k);
		}

	}

	private boolean hasChild(int i) {
		return (i * 2 + 1) < size;
	}

	private int getParent(int i) {
		return (i - 1) / 2;
	}

	private int getMaximumChild(int i) {
		if ((i * 2 + 2) < size) {
			return heap[i * 2 + 1].compareTo(heap[i * 2 + 2]) > 0 ? i * 2 + 1
					: i * 2 + 2;
		} else if (i * 2 + 1 < size) {
			return i * 2 + 1;
		} else {
			return -1;
		}
	}

	public String toString() {
		String str = "";
		for (int i = 0; i < size; i++) {
			str += i + " : " + heap[i] + "\n";
		}
		return str;
	}

	public boolean isEmpty() {
		return 0 == size;
	}

	public static void main(String[] args) {
		/*
		 * MaxHeap h = new MaxHeap();
		 * java.util.Random rand = new
		 * java.util.Random();
		 * int a[] = new int[20];
		 * for (int i = 0; i < 20; i++) {
		 * a[i] = rand.nextInt(100);
		 * h.insert(a[i]);
		 * }
		 * Arrays.sort(a);
		 * while(!h.isEmpty())
		 * {
		 * System.out.print(h.ExtractMax()+" ");
		 * }
		 * System.out.println();
		 * for(int i:a)
		 * {
		 * System.out.print(i+" ");
		 * }
		 */
	}
}