힙을 이용한 트리

힙을 이용하여 트리를 만들어 본다

자바로 작성함

트리는 중위순회로 확인해본다.

 

class Heap {

private int heapSize;

private int itemHeap[];

 

public Heap() {

heapSize = 0;

itemHeap = new int[50];

}

 

public void insertHeap(int item) {

int i = ++heapSize;

while ((i != 1) && (item > itemHeap[i / 2])) {

itemHeap[i] = itemHeap[i / 2];

i /= 2;

}

itemHeap[i] = item;

}

 

public int getHeapSize() {

return this.heapSize;

}

 

public int deleteHeap() {

int parent, child;

int item, temp;

item = itemHeap[1];

temp = itemHeap[heapSize--];

parent = 1;

child = 2;

 

while (child <= heapSize) {

if ((child < heapSize) && (itemHeap[child] < itemHeap[child + 1]))

child++;

if (temp >= itemHeap[child])

break;

 

itemHeap[parent] = itemHeap[child];

parent = child;

child *= 2;

}

itemHeap[parent] = temp;

return item;

}

 

public void inorder(int i) {

int k = heapSize;

 

 

if (i <= k) {

 

inorder(i * 2);

System.out.print(itemHeap[i]+" ");

inorder(i * 2 + 1);

 

}

}

 

public void printHeap() {

System.out.printf("\nHeap >>> ");

for (int i = 1; i <= heapSize; i++)

System.out.printf("[%d] ", itemHeap[i]);

}

}

 

class data {

public static void main(String args[]) {

int n,item,k=1;

Heap h = new Heap();

 

h.insertHeap(34);

h.insertHeap(56);

h.insertHeap(23);

h.insertHeap(39);

h.insertHeap(55);

h.insertHeap(78);

h.insertHeap(12);

h.insertHeap(14);

h.insertHeap(29);

h.insertHeap(50);

System.out.print("입력확인");

h.printHeap();

System.out.println("\n중위순회");

h.inorder(k);

System.out.println("\n내림차순정렬");

n = h.getHeapSize();

for (int i = 1; i <= n; i++) {

item = h.deleteHeap();

System.out.print(item+ " ");

}

}

}