일반적인 Max Heap 소스는 1차원 배열을 이용한 것이다.
여기서는 Node와 Node간의 연결을 Class로 구현하여 Max Heap을 구성해본다.
|
package com.eugeneprogram.maxheap;
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.maxheap;
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.maxheap;
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()); } } } } /* * node를 반환한다. */ return node; }
/* * 노드를 크기 순서대로 정렬해주는 명령어. */ 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; } } }
public void levelorder(Node node) { /* * 새로운 Queue인 queue 생성. * node값을 queue에 추가. */ Queue queue = new Queue(); queue.push(node);
/* * queue가 공백이 아닐경우 반복실행. * queue의 맨앞에 값을 삭제하고 반환하여 tempNode에 대입. * tempNode의 값을 출력. */ while(!queue.isEmpty()) { Node tempNode = (Node) queue.pop(); System.out.print(tempNode.getData() + " "); /* * tempNode의 왼쪽자식노드가 공백이 아닐경우 실행. * tempNode의 왼쪽자식노드를 queue에 추가. */ if(tempNode.getLeftChild() != null) { queue.push(tempNode.getLeftChild()); } /* * tempNode의 오른쪽자식노드가 공백이 아닐경우 실행. * tempNode의 오른쪽자식노드를 queue에 추가. */ if(tempNode.getRightChild() != null) { queue.push(tempNode.getRightChild()); } } } } |
|
package com.eugeneprogram.maxheap;
public class MaxHeapTest { public static void main(String[] args) { /* * MaxHeap인 tree 생성. * 노드 tempNode 생성. */ MaxHeap tree = new MaxHeap(); Node tempNode;
/* * tree에 노드 1 추가한 후, tempNode에 대입. * tempNode를 maxHeap 적용. * tree의 rootNode에 levelorder 실행. */ tempNode = tree.addNode(1); tree.maxHeap(tempNode); tree.levelorder(tree.rootNode); System.out.println(); System.out.println("==================");
/* * tree에 노드 2 추가한 후, tempNode에 대입. * tempNode를 maxHeap 적용. * tree의 rootNode에 levelorder 실행. */ tempNode = tree.addNode(2); tree.maxHeap(tempNode); tree.levelorder(tree.rootNode); System.out.println(); System.out.println("==================");
/* * tree에 노드 3 추가한 후, tempNode에 대입. * tempNode를 maxHeap 적용. * tree의 rootNode에 levelorder 실행. */ tempNode = tree.addNode(3); tree.maxHeap(tempNode); tree.levelorder(tree.rootNode); System.out.println(); System.out.println("==================");
/* * tree에 노드 4 추가한 후, tempNode에 대입. * tempNode를 maxHeap 적용. * tree의 rootNode에 levelorder 실행. */ tempNode = tree.addNode(4); tree.maxHeap(tempNode); tree.levelorder(tree.rootNode); System.out.println(); System.out.println("==================");
/* * tree에 노드 5 추가한 후, tempNode에 대입. * tempNode를 maxHeap 적용. * tree의 rootNode에 levelorder 실행. */ tempNode = tree.addNode(5); tree.maxHeap(tempNode); tree.levelorder(tree.rootNode); System.out.println(); System.out.println("==================");
/* * tree에 노드 6 추가한 후, tempNode에 대입. * tempNode를 maxHeap 적용. * tree의 rootNode에 levelorder 실행. */ tempNode = tree.addNode(6); tree.maxHeap(tempNode); tree.levelorder(tree.rootNode); System.out.println(); System.out.println("==================");
/* * tree에 노드 7 추가한 후, tempNode에 대입. * tempNode를 maxHeap 적용. * tree의 rootNode에 levelorder 실행. */ tempNode = tree.addNode(7); tree.maxHeap(tempNode); tree.levelorder(tree.rootNode); System.out.println(); System.out.println("==================");
/* * tree에 노드 8 추가한 후, tempNode에 대입. * tempNode를 maxHeap 적용. * tree의 rootNode에 levelorder 실행. */ tempNode = tree.addNode(8); tree.maxHeap(tempNode); tree.levelorder(tree.rootNode); System.out.println(); System.out.println("=================="); } } |
설명은 주석으로 대체한다.
Programmed by 김지훈(교통대)
댓글 0
| 번호 | 제목 | 글쓴이 | 날짜 | 조회 수 |
|---|---|---|---|---|
| 12 | Java 기초 - Parameter를 가진 메쏘드의 선언 | Eugene | 2025.04.16 | 34 |
| 11 | Java 기초 - 메쏘드를 가진 클래스의 선언과 클래스의 객체를 예시화(instantiate)하기 | Eugene | 2024.03.25 | 59 |
| 10 | Java Heap Sort(힙 정렬) | Eugene | 2022.04.12 | 309 |
| » | Java Max Heap(자바 맥스 힙) | Eugene | 2021.09.16 | 221 |
| 8 | Java - Binary Tree(자바 이진 트리) | Eugene | 2021.08.17 | 276 |
| 7 | Java Tree(자바 트리) - 자식 노드들을 리스트 자료구조를 사용하여 구현 | Eugene | 2021.04.01 | 2539 |
| 6 | JAVA Linked List(링크드 리스트) [1] | Eugene | 2021.02.09 | 792 |
| 5 | Java 기초 - 재귀 함수를 이용한 최대값 구하기 | Eugene | 2019.05.14 | 1101 |
| 4 | Java 기초 - while, for [2] | Eugene | 2018.04.05 | 860 |
| 3 | Java 기초 - 조건문 if | Eugene | 2017.11.03 | 757 |
| 2 | Java 기초 - 두 정수 입력 받아 합 구하기 | Eugene | 2017.11.01 | 3771 |
| 1 | Java 기초 - Hello, World! | Eugene | 2017.09.27 | 1780 |