최대 힙 최소 힙

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

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

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

view source

print?

001	import java.util.Arrays;

002

003	public class MinHeap<t comparable<t="" extends="">> {

004	private T[] heap = null;

005	private int size = 0;

006

007	@SuppressWarnings("unchecked")

008	public MinHeap() {

009	heap = (T[]) new Comparable[1024];

010

}

011

012	public boolean isEmpty() {

013	return size == 0;

014

}

015

016	public void insert(T element) {

017	if (size >= heap.length) {

018	T[] temp = Arrays.copyOf(heap, heap.length * 2);

019	heap = temp;

020

}

021	heap[size] = element;

022	int i = size;

023	int p = getParent(i);

024	while (p >= 0 && heap[p].compareTo(heap[i]) > 0) {

025	T temp = heap[i];

026	heap[i] = heap[p];

027	heap[p] = temp;

028

i = p;

029	p = getParent(p);

030

}

031

size++;

032

}

033

034	public T getMinimun() {

035	return heap[0];

036

}

037

038	public T ExtractMin() {

039	T min = heap[0];

040

size--;

041	heap[0] = heap[size];

042	heapify(0);

043	return min;

044

}

045

046	private void heapify(int i) {

047	if (!hasChild(i))

048

return;

049	int k = getMinimumChild(i);

050	if (heap[i].compareTo(heap[k]) > 0) {

051	T temp = heap[i];

052	heap[i] = heap[k];

053	heap[k] = temp;

054	heapify(k);

055

}

056

057

}

058

059	private boolean hasChild(int i) {

060	return (i * 2 + 1) < size;

061

}

062

063	private int getParent(int i) {

064	return (i - 1) / 2;

065

}

066

067	private int getMinimumChild(int i) {

068	if ((i * 2 + 2) < size) {

069	return heap[i * 2 + 1].compareTo(heap[i * 2 + 2]) < 0 ? i * 2 + 1

070	: i * 2 + 2;

071	} else if (i * 2 + 1 < size) {

072	return i * 2 + 1;

073

} else {

074	return -1;

075

}

076

}

077

078	public String toString() {

079	String str = "";

080	for (int i = 0; i < size; i++) {

081	str += i + " : " + heap[i] + "\n";

082

}

083	return str;

084

}

085

086	public static void main(String[] args) {

087

088

/*

089	* MinHeap<integer> h = new MinHeap<integer>();

090	* java.util.Random rand = new

091	* java.util.Random();

092	* int a[] = new int[20];

093	* for (int i = 0; i < 20; i++) {

094	* a[i] = rand.nextInt(100);

095	* h.insert(a[i]);

096

* }

097	* Arrays.sort(a);

098	* while(!h.isEmpty())

099

* {

100	* System.out.print(h.ExtractMin()+" ");

101

* }

102	* System.out.println();

103	* for(int i:a)

104

* {

105	* System.out.print(i+" ");

106

* }

107

*/

108

}

109

}

110	</integer></integer></t>

 

view source

print?

001	import java.util.Arrays;

002

003	public class MaxHeap<t comparable<t="" extends="">> {

004	private T[] heap = null;

005	private int size = 0;

006

007	@SuppressWarnings("unchecked")

008	public MaxHeap() {

009	heap = (T[]) new Comparable[1024];

010

}

011

012	public void insert(T element) {

013	if (size >= heap.length) {

014	T[] temp = Arrays.copyOf(heap, heap.length * 2);

015	heap = temp;

016

}

017	heap[size] = element;

018	int i = size;

019	int p = getParent(i);

020	while (p >= 0 && heap[p].compareTo(heap[i]) < 0) {

021	T temp = heap[i];

022	heap[i] = heap[p];

023	heap[p] = temp;

024

i = p;

025	p = getParent(p);

026

}

027

size++;

028

}

029

030	public T getMaximun() {

031	return heap[0];

032

}

033

034	public T ExtractMax() {

035	T max = heap[0];

036

size--;

037	heap[0] = heap[size];

038	heapify(0);

039	return max;

040

}

041

042	private void heapify(int i) {

043	if (!hasChild(i))

044

return;

045	int k = getMaximumChild(i);

046	if (heap[i].compareTo(heap[k]) < 0) {

047	T temp = heap[i];

048	heap[i] = heap[k];

049	heap[k] = temp;

050	heapify(k);

051

}

052

053

}

054

055	private boolean hasChild(int i) {

056	return (i * 2 + 1) < size;

057

}

058

059	private int getParent(int i) {

060	return (i - 1) / 2;

061

}

062

063	private int getMaximumChild(int i) {

064	if ((i * 2 + 2) < size) {

065	return heap[i * 2 + 1].compareTo(heap[i * 2 + 2]) > 0 ? i * 2 + 1

066	: i * 2 + 2;

067	} else if (i * 2 + 1 < size) {

068	return i * 2 + 1;

069

} else {

070	return -1;

071

}

072

}

073

074	public String toString() {

075	String str = "";

076	for (int i = 0; i < size; i++) {

077	str += i + " : " + heap[i] + "\n";

078

}

079	return str;

080

}

081

082	public boolean isEmpty() {

083	return 0 == size;

084

}

085

086	public static void main(String[] args) {

087

/*

088	* MaxHeap<integer> h = new MaxHeap<integer>();

089	* java.util.Random rand = new

090	* java.util.Random();

091	* int a[] = new int[20];

092	* for (int i = 0; i < 20; i++) {

093	* a[i] = rand.nextInt(100);

094	* h.insert(a[i]);

095

* }

096	* Arrays.sort(a);

097	* while(!h.isEmpty())

098

* {

099	* System.out.print(h.ExtractMax()+" ");

100

* }

101	* System.out.println();

102	* for(int i:a)

103

* {

104	* System.out.print(i+" ");

105

* }

106

*/

107

}

108	}</integer></integer></t>