package com.eugeneprogram.sort;

import java.util.ArrayList;

public class Queue {

private ArrayList <Object>queue; //queue를 배열로 구성

public Queue() {

queue = new  ArrayList<Object>();

}

/*

* queue에 추가 명령어.

*/

public void push(Object o) {

queue.add(o);

}

/*

* queue의 맨앞에 값 삭제 명령어.

*/

public Object pop() {

return queue.remove(0);

}

/*

* queue가 공백인지 아닌지 판별하는 명령어.

* queue가 공백이거나 크기가 0일경우 true 반환, 그렇지 않으면 false 반환.

*/

public boolean isEmpty() {

if (null == queue || queue.size() == 0)

return true;

else

return false;

}

}

package com.eugeneprogram.sort;

public class Node {

private int data; //노드의 값

private Node leftChild; //왼쪽 자식 노드

private Node rightChild; //오른쪽 자식 노드

private Node parentNode; //부모 노드

public Node(int data) {

this.data = data;

this.parentNode = null;

this.leftChild= null;

this.rightChild = null;

}

/*

* 부모노드 조회.

*/

public Node getParent(Node parent) {

return this.parentNode;

}

/*

* 왼쪽 자식 노드 조회.

*/

public Node getLeftChild() {

return this.leftChild;

}

/*

* 데이터 조회.

*/

public int getData() {

return data;

}

/*

* 데이터 설정.

*/

public void setData(int data) {

this.data = data;

}

/*

* 오른쪽 자식 노드 조회.

*/

public Node getRightChild() {

return rightChild;

}

/*

* 부모 노드 설정.

*/

public void setParent(Node parent) {

this.parentNode = parent;

}

/*

* 오른쪽 자식 노드 설정.

*/

public void setRightChild(Node rightChild) {

this.rightChild = rightChild;

}

/*

* 왼쪽 자식 노드 설정.

*/

public void setLeftChild(Node leftChild) {

this.leftChild = leftChild;

}

}

package com.eugeneprogram.sort;

import java.util.ArrayList;

import com.eugeneprogram.sort.Node;

import com.eugeneprogram.sort.Queue;

public class MaxHeap {

/*

* 노드의 rootNode를 공백으로 만든다.

*/

Node rootNode = null; /*

* 노드를 추가하는 명령어.

*/

public Node addNode(int data) {

/*

* rootNode가 공백일 경우 실행.

* 정수형 data를 노드로 바꾼 후 rootNode에 대입한다.

* rootNode를 반환한다.

*/

if(rootNode == null) {

rootNode = new Node(data);

return rootNode;

} 

/*

* rootNode가 공백이 아닐 경우 실행.

* 새로운 Queue인 queue를 생성.

* queue에 rootNode의 값 추가.

*/

else {

Queue queue = new Queue();

queue.push(rootNode);

/*

* queue가 공백이 아닐 경우 while 반복문 실행.

* queue의 맨 앞에 값을 삭제하고 반환하여 tmepNode에 대입한다.

*/

while (!queue.isEmpty()) {

Node tempNode = (Node) queue.pop();

/*

* tempNode의 왼쪽 자식노드가 공백 아닐 경우 실행.

* queue에 tempNode의 왼쪽 자식노드의 값을 추가.

*/

if (tempNode.getLeftChild() != null) {

queue.push(tempNode.getLeftChild());

/*

* tempNode의 오른쪽 자식노드가 공백이 아닐 경우 실행.

* queue에 tempNode의 오른쪽 자식노드의 값을 추가.

*/

if (tempNode.getRightChild() != null) {

queue.push(tempNode.getRightChild());

}

/*

* tempNode의 오른쪽 자식노드가 공백일 경우 실행.

* 노드인 childNode에 정수형 data값을 노드로 바꾼 후 대입한다.

* tempNode의 오른쪽 자식노드를 childNode로 설정한다.

* childNode를 반환한다.

*/

else {

Node childNode = new Node(data); 

tempNode.setRightChild(childNode);

return childNode;

}

}

/*

* tempNode의 왼쪽 자식노드가 공백일 경우 실행.

* 노드인 childNode에 정수형 data값을 노드로 바꾼 후 대입한다.

* tempNode의 왼쪽 자식노드를 childNode로 설정한다.

* childNode를 반환한다.

*/

else {

Node childNode = new Node(data); 

tempNode.setLeftChild(childNode);

return childNode;

}

}

}

/*

* rootNode를 반환한다.

*/

return rootNode;

}

/*

* 노드의 부모노드를 찾는 명령어.

*/

public Node getParent(Node node) {

/*

* 새로운 Queue인 queue를 생성.

* queue에 rootNode의 값 추가.

*/

Queue queue = new Queue();

queue.push(rootNode);

/*

* queue가 공백이 아닐경우 while반복문 실행.

* queue의 맨 앞에 값을 삭제하고 반환하여 tmepNode에 대입한다.

*/

while(!queue.isEmpty()) {

Node tempNode = (Node) queue.pop();

/*

* tempNode의 왼쪽 자식노드가 공백이고, tempNode의 오른쪽 자식노드가 공백일 경우 실행.

* while반복문 중단.

*/

if(tempNode.getLeftChild() == null && tempNode.getRightChild() == null) {

break;

}

/*

* tempNode의 왼쪽 자식노드가 공백이 아니고, tempNode의 오른쪽 자식노드가 공백이 아닐 경우 실행.

*/

else {

/*

* (tempNode의 왼쪽 자식노드가 공백이 아니고, tempNode의 왼쪽 자식노드의 값이 node의 값이랑 일치) 하거나

* (tempNode의 오른쪽 자식노드가 공백이 아니고, tempNode의 오른쪽 자식노드의 값이 node의 값이랑 일치)할 경우 실행.

*/

if ((null != tempNode.getLeftChild() &&

tempNode.getLeftChild().getData() == node.getData()) ||

(null != tempNode.getRightChild() &&

tempNode.getRightChild().getData() == node.getData())

) {

/*

* 노드인 parentNode에 tempNode 대입.

* parentNode 반환.

*/

Node parentNode = tempNode;

return parentNode;

/*

* (tempNode의 왼쪽 자식노드가 공백이고, tempNode의 왼쪽 자식노드의 값이 node의 값이랑 불일치) 하거나

* (tempNode의 오른쪽 자식노드가 공백이고, tempNode의 오른쪽 자식노드의 값이 node의 값이랑 불일치)할 경우 실행.

*/

} else {

/*

* tempNode의 왼쪽 자식노드의 값이 공백이 아닐경우 실행.

* queue에 tempNode의 왼쪽 자식노드 값을 추가.

*/

if(tempNode.getLeftChild() != null) {

queue.push(tempNode.getLeftChild());

}

/*

* tempNode의 오른쪽 자식노드의 값이 공백이 아닐경우 실행.

* queue에 tempNode의 오른쪽 자식노드 값을 추가.

*/

if(tempNode.getRightChild() != null) {

queue.push(tempNode.getRightChild());

}

}

}

}

/*

* queue가 비었다면, null을 반환한다.

*/

return null;

}

/*

* 노드를 크기 순서대로 정렬해주는 명령어.

*/

public void maxHeap(Node currentNode) {

/*

* 노드인 parentNode에 currentNode의 부모를 대입.

*/

Node parentNode = getParent(currentNode);

/*

* parentNode가 공백이 아닐 경우 while반복문 실행.

*/

while(parentNode != null) {

/*

* currentNode의 값이 parentNode의 값보다 클 경우 실행.

*/

if(currentNode.getData() > parentNode.getData()) {

/*

* 정수형 a에 currentNode의 값을 대입한다.

* 정수형 b에 parentNode의 값을 대입한다.

*/

int a = currentNode.getData();

int b = parentNode.getData();

/*

* 노드 값만 swap.

* currentNode에 값을 b(=parentNode의 값)로 설정.

* parentNode의 값을 a(=currentNode의 값)로 설정. 

*/

currentNode.setData(b);

parentNode.setData(a);

/*

* currentNode에 parentNode 삽입.

* parentNode에 currentNode의 부모노드 삽입.

*/

currentNode = parentNode;

parentNode = getParent(currentNode);

}

/*

* currentNode의 값이 parentNode의 값보다 작을 경우 실행.

* while반복문 중단.

*/

else {

break;

}

}

}

ArrayList <Integer> maxHeap = new ArrayList<Integer>();

public ArrayList<Integer> levelorder() {

/*

* 새로운 Queue인 queue 생성.

* node값을 queue에 추가.

*/

Queue queue = new Queue();

queue.push(rootNode);

/*

* queue가 공백이 아닐경우 반복실행.

* queue의 맨앞에 값을 삭제하고 반환하여 tempNode에 대입.

* temp노드의 값을 ArrayList인 maxHeap에 추가.

*/

while(!queue.isEmpty()) {

Node tempNode = (Node) queue.pop();

maxHeap.add(tempNode.getData());

/*

* tempNode의 왼쪽자식노드가 공백이 아닐경우 실행.

* tempNode의 왼쪽자식노드를 queue에 추가.

*/

if(tempNode.getLeftChild() != null) {

queue.push(tempNode.getLeftChild());

}

/*

* tempNode의 오른쪽자식노드가 공백이 아닐경우 실행.

* tempNode의 오른쪽자식노드를 queue에 추가.

*/

if(tempNode.getRightChild() != null) {

queue.push(tempNode.getRightChild());

}

}

/*

* maxHeap반환.

*/

return maxHeap;

}

}

package com.eugeneprogram.sort;

import java.util.ArrayList;

import com.eugeneprogram.sort.MaxHeap;

import com.eugeneprogram.sort.Node;

public class HeapSort {

/*

* HeapSort할 배열들 설정.

*/

int[] sortList = {8, 65, 2, 90, 61, 55, 7};

/*

* HeapSort적용한 ArrayList인 list.

*/

ArrayList<Integer> list = new ArrayList<Integer>();

/*

* HeapSort를 실행할 명령어. 

*/

public void adjust() {

/*

* (sortList의 길이 - 1)번 for반복문 실행.

* 새로운 Heap인 MH생성.

*/

for(int i = 0; i < sortList.length - 1; i++) {

MaxHeap MH = new MaxHeap();  

/*

* (sortList의 길이 - i)번 for반복문 실행.

* sortList의 j번째 원소를 addNode실행한 후 Node인 tempNode에 대입.

* 대입 된 tempNode들을 maxHeap실행.

*/

for(int j = 0; j < sortList.length - i; j++) {

Node tempNode = MH.addNode(sortList[j]);

MH.maxHeap(tempNode);

}

System.out.println();

/*

* MaxHeap을 적용한 노드를 ArrayList로 적용 후 list에 대입.

* (list의 길이)번 for반복문 실행.

* list의 k번째 원소를 sortList의 k번째에 대입.

*/

list = MH.levelorder();

int k = 0;

for (; k < list.size(); ++k) {

sortList[k] = list.get(k);

}

/*

* swap

* 정수형 temp에 sortList의 0번째 원소 대입.

* sortList의 0번째에 sortList의 k-1번째(맨 끝)원소 대입.

* sortList의 k-1번째(맨 끝)에 정수형 temp대입.

*/

int temp = sortList[0];

sortList[0] = sortList[k - 1];

sortList[k - 1] = temp;

/*

* sortList를 출력.

*/

for(int l = 0; l < 7; l++) {

System.out.print(sortList[l] + " ");

}

}

System.out.println();

}

}

package com.eugeneprogram.sort;

public class HeapSortTest {

public static void main(String[] args) {

/*

* HeapSort인 HS 생성

*/

HeapSort HS = new HeapSort();

/*

* adjust 명령어 실행.

*/

HS.adjust();

}

}