잘못된 정보가 있다면, 꼭 댓글로 알려주세요(비로그인 익명도 가능).
여러분의 피드백이 저와 방문자 모두를 올바른 정보로 인도할 수 있습니다.
감사합니다. -
후원해주실 분은 여기로→
현록의 기록저장소
기본 알고리듬 본문
[이동용 목차] (항목 클릭)
ㆁ소수(Prime Number)
＊소수란
＊소수 판별 - 에라토스테네스의 체 (Sieve of Eratosthenes)
ㆁ최대공약수(greastest common divisor, GCD)
＊유클리드 호제법 (Euclidean algorithm)
＊𝑛개의 수의 공통 최대공약수
ㆁ최소공배수(least common multiple, LCM)
＊𝑛개의 수의 공통 최소공배수
ㆁ이진 탐색 (Binary Search)
ㆁ버블 정렬 (Bubble Sort)
ㆁ선택 정렬 (Selection Sort)
＊기본
＊개선 1: 순회할 때 최소와 최대를 동시에
＊개선 2: 같은 최솟값은 한꺼번에
ㆁ삽입 정렬 (Insertion Sort)
ㆁ퀵 정렬 (Quick Sort)
ㆁ합병 정렬 (Merge Sort)
ㆁ힙 정렬 (Heap Sort)
ㆁ소수(Prime Number)
＊소수란
ㆍ1보다 큰 자연수 중, 1과 자기 자신만을 약수로 갖는 수 (1과 자기 자신으로만 나머지가 0으로 나눠 떨어지는 수)
ㆍex) 2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 37, 41, ...
ㆍ짝수는 모두 2의 배수이기 때문에, 2를 제외하고는 모두 홀수이다. 하지만 2는 소수에 포함된다.
ㆍ유클리드의 정리 (Euclid's theorem)에 의하면, 소수는 무한히 존재한다.
ㆍ반대의 개념은 합성수(Composite Number)
ㆍhttps://en.wikipedia.org/wiki/Prime_number
ㆍhttps://ko.wikipedia.org/wiki/소수_(수론)
ㆍhttps://en.wikipedia.org/wiki/Euclid's_theorem
ㆍhttps://ko.wikipedia.org/wiki/유클리드의_정리
＊에라토스테네스의 체 (Sieve of Eratosthenes)
ㆍ고대 그리스 수학자 에라토스테네스가 발견한, 소수를 찾는 방법(알고리듬)
ㆍhttps://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
ㆍhttps://ko.wikipedia.org/wiki/에라토스테네스의_체
public int[] getPrimeNumbersBySieveOfEratosthenes(int max) {
// boolean은 false로 초기화되므로, '소수가 아니다'의 false는 '소수이다'로 시작.
boolean[] isNotPrimeNumber = new boolean[max];
isNotPrimeNumber[0] = true; // 1은 소수가 아님
for (int i = 2; i * i <= max; ++i) {
for (int j = i * i; j <= max; j += i) { // i * 2 부터 시작이 아니라, i * i 부터 시작. i * i 이전의 i의 배수들은 이전 과정에서 체크되었음.
isNotPrimeNumber[j - 1] = true; // 자기 자신을 제외한, 자신의 배수들은 모두 소수가 아님.
}
}
// 소수들의 갯수
int count = 0;
for (int i = 0; i < isNotPrimeNumber.length; ++i) {
if (isNotPrimeNumber[i] == false) {
++count;
}
}
// 소수들을 담아 반환할 int[] 배열
int[] primeNumbers = new int[count];
int index = 0;
for (int i = 0; i < isNotPrimeNumber.length && index < count; ++i) {
if (isNotPrimeNumber[i] == false) {
primeNumbers[index++] = i + 1;
}
}
return primeNumbers;
}private boolean[] getBooleanArrayMeansNotPrimeNumbers(int max) {
// boolean은 false로 초기화되므로, '소수가 아니다'의 false는 '소수이다'로 시작.
boolean[] isNotPrimeNumber = new boolean[max];
isNotPrimeNumber[0] = true; // 1은 소수가 아님
for (int i = 2; i * i <= max; ++i) {
for (int j = i * i; j <= max; j += i) { // i * 2 부터 시작이 아니라, i * i 부터 시작. i * i 이전의 i의 배수들은 이전 과정에서 체크되었음.
isNotPrimeNumber[j - 1] = true; // 자기 자신을 제외한, 자신의 배수들은 모두 소수가 아님.
}
}
return isNotPrimeNumber;
}
public int getCountOfPrimeNumbers(int max) {
return getCountOfPrimeNumbers(max, getBooleanArrayMeansNotPrimeNumbers(max));
}
private int getCountOfPrimeNumbers(int max, boolean[] isNotPrimeNumber) {
// 소수들의 갯수
int count = 0;
for (int i = 0; i < isNotPrimeNumber.length; ++i) {
if (isNotPrimeNumber[i] == false) {
++count;
}
}
return count;
}
public int[] getIntegerArrayMeansPrimeNumbers(int max) {
boolean[] isNotPrimeNumber = getBooleanArrayMeansNotPrimeNumbers(max);
int count = getCountOfPrimeNumbers(max, isNotPrimeNumber);
// 소수들을 담아 반환할 int[] 배열
int[] primeNumbers = new int[max];
int index = 0;
for (int i = 0; i < isNotPrimeNumber.length && index < count; ++i) {
if (isNotPrimeNumber[i] == false) {
primeNumbers[index++] = i + 1;
}
}
return primeNumbers;
}
ㆁ최대공약수(greastest common divisor, GCD)
＊유클리드 호제법 (Euclidean algorithm)
ㆍ서로 호(互), 나눌 제(除). 두 개의 양의 정수간의 최대공약수를 구함.
ㆍ𝑎와 𝑏의 최대공약수는,
𝑎 = 𝑏*𝑞 + 𝑟 (𝑟은 𝑏미만의 나머지 형태)
↙ ↙
𝑏 = 𝑟*𝑝 + 𝑠
↙ ↙
𝑟 = 𝑠*𝑡 + 𝑢... 를 반복하다가, 상수항(나머지)이 없을 때의 계수가 최대공약수
ㆍ570 = 36×15 + 30
36 = 30×1 + 6
30 = 6×5
→ ∴ 6
ㆍhttps://en.wikipedia.org/wiki/Euclidean_algorithm
ㆍhttps://ko.wikipedia.org/wiki/유클리드_호제법
public int getGCDbyEuclideanAlgorithm(int number1, int number2) {
if (number1 == number2) {
return number1;
}
int big = 0;
int small = 0;
if (number1 > number2) {
big = number1;
small = number2;
} else {
big = number2;
small = number1;
}
while (true) {
int residue = big % small;
if (residue == 0) {
return small;
} else {
big = small;
small = residue;
}
}
}
＊𝑛개의 수를 소인수분해하여, 각 수의 소수들 중 공통되는 부분들만 가장 큰 형태로.
ㆍ소수는 아니지만, 최소 1은 공통될 수 있으니, 구하려던 수들이 서로소라면 최대공약수는 1이된다.
ㆍ60 = 22×3×5
24 = 23×3
20 = 22×5
→ ∴ 22 = 4
public int getGCD(int[] numbers) {
if (numbers.length == 1) {
return numbers[0];
}
int answer = 1;
HashMap<Integer, Integer>[] primeNumbers = new HashMap[numbers.length]; // 각각의 소인수분해 결과를 <Key: 밑, Value: 지수> 형태로 담음
for (int i = 0; i < numbers.length; ++i) {
primeNumbers[i] = new HashMap<>();
int thisNumber = numbers[i];
int divisor = 2;
while (thisNumber > 1) {
if (thisNumber % divisor == 0) {
if (primeNumbers[i].containsKey(divisor)) {
primeNumbers[i].put(divisor, primeNumbers[i].get(divisor) + 1);
} else {
primeNumbers[i].put(divisor, 1);
}
thisNumber /= divisor;
} else {
++divisor;
}
}
}
loop1:
for (Integer primeNumber : primeNumbers[0].keySet()) { // 공통되어야 하므로, 아무 결과를 하나로 기준으로 해도 됨.
for (int i = 1; i < numbers.length; ++i) {
if (primeNumbers[i].containsKey(primeNumber) == false) { // 소수를 공통으로 지니지 않으면 해당 소수는 결과에 포함되지 않음.
continue loop1;
}
}
int maxCommonPower = primeNumbers[0].get(primeNumber); // 지수는 Value들 중의 최소값으로.
for (int i = 1; i < numbers.length; ++i) {
int power = primeNumbers[i].get(primeNumber);
if (power < maxCommonPower) {
maxCommonPower = power;
}
}
for (int i = 0; i < maxCommonPower; ++i) {
answer *= primeNumber;
}
}
return answer;
}
ㆁ최소공배수(least common multiple, LCM)
＊𝑛개의 수를 소인수분해하여, 각 수의 소수들은 모두 포함하되, 승수는 가장 높도록.
ㆍ60 = 22×3×5
37 = 37
24 = 23×3
→ ∴ 23×3×5×37 = 4440
ㆍ[Lv2] N개의 최소공배수 (https://ydeer.tistory.com/36)
public int getLCM(int[] numbers) {
if (numbers.length == 1) {
return numbers[0];
}
int answer = 1;
HashMap<Integer, Integer>[] primeNumbers = new HashMap[numbers.length]; // 각각의 소인수분해 결과를 <Key: 밑, Value: 지수> 형태로 담음
for (int i = 0; i < numbers.length; ++i) {
primeNumbers[i] = new HashMap<>();
int thisNumber = numbers[i];
int divisor = 2;
while (thisNumber > 1) {
if (thisNumber % divisor == 0) {
if (primeNumbers[i].containsKey(divisor) == true) { // 이미 존재하면, 기존보다 +1승.
primeNumbers[i].put(divisor, primeNumbers[i].get(divisor) + 1);
} else {
primeNumbers[i].put(divisor, 1); // 최초라면 1번째 등장이니 1승.
}
thisNumber /= divisor;
} else {
++divisor;
}
}
}
HashMap<Integer, Integer> results = new HashMap<>(); // 결과를 <Key: 밑, Value: 지수> 형태로 저장해 둠. 지수가 점점 커질 수 있으니 저장하면서 진행.
for (int i = 0; i < numbers.length; ++i) { // 소인수분해 결과 중 소수(밑. Key)는 어쨌든 다 사용.
for (Integer base : primeNumbers[i].keySet()) {
int thisPower = primeNumbers[i].get(base);
if (results.containsKey(base) == true) { // 이미 결과에 밑(Key)이 있었으면, 큰 지수(Value) 계산 후 저장.
int resultsPower = results.get(base);
if (thisPower > resultsPower) {
results.put(base, thisPower);
}
} else { // 최초라면 우선 그냥 저장(소수는 어쨌든 다 사용).
results.put(base, thisPower);
}
}
}
for (Integer base : results.keySet()) {
for (int i = 0; i < results.get(base); ++i) {
answer *= base;
}
}
return answer;
}
ㆁ이진 탐색 (Binary Search)
ㆍhttps://en.wikipedia.org/wiki/Binary_search_algorithm
ㆍhttps://ko.wikipedia.org/wiki/이진_검색_알고리즘
public int binarySearchRecursive(int integers[], int target) {
return binarySearchRecursiveCore(integers, 0, integers.length - 1, target);
}
private int binarySearchRecursiveCore(int integers[], int indexStart, int indexEnd, int target) {
if (indexStart > indexEnd) {
return -1;
} else {
int indexMiddle = (indexStart + indexEnd) / 2;
if (integers[indexMiddle] == target) {
return indexMiddle;
} else if (integers[indexMiddle] < target) {
return binarySearchRecursiveCore(integers, indexMiddle + 1, indexEnd, target);
} else {
return binarySearchRecursiveCore(integers, indexStart, indexMiddle - 1, target);
}
}
}
public int binarySearchLoop(int integers[], int target) {
int indexStart = 0;
int indexEnd = integers.length - 1;
while (indexStart <= indexEnd) {
int indexMiddle = (indexStart + indexEnd) / 2;
if (integers[indexMiddle] == target) {
return indexMiddle;
} else if (integers[indexMiddle] < target) {
indexStart = indexMiddle + 1;
} else {
indexEnd = indexMiddle - 1;
}
}
return -1;
}
ㆁ버블 정렬 (Bubble Sort)
ㆍhttps://ko.wikipedia.org/wiki/거품_정렬
ㆍhttps://en.wikipedia.org/wiki/Bubble_sort
ㆍhttps://namu.wiki/w/정렬 알고리즘?from=버블 정렬#s-2.1.1
ㆍ시간 복잡도: 𝑂(𝑛2)
ㆍ공간 복잡도: 𝑂(1)
ㆍ안정성: 보장 됨 (O)
public void bubbleSort(int[] integers) {
for (int i = 0; i < integers.length - 1; ++i) {
for (int j = 0; j < integers.length - 1 - i; ++j) {
if (integers[j] > integers[j + 1]) {
int temp = integers[j];
integers[j] = integers[j + 1];
integers[j + 1] = temp;
}
}
}
}
ㆁ선택 정렬 (Selection Sort)
＊기본
ㆍhttps://en.wikipedia.org/wiki/Selection_sort
ㆍhttps://ko.wikipedia.org/wiki/선택_정렬
ㆍhttps://namu.wiki/w/정렬 알고리듬?from=선택 정렬#s-2.1.2
ㆍ시간 복잡도: 𝑂(𝑛2)
ㆍ공간 복잡도: 𝑂(1)
ㆍ안정성: 보장 안 됨 (X)
public void selectionSort(int[] integers) {
for (int i = 0; i < integers.length - 1; ++i) {
int indexMin = i;
// for (int j = i + 1; j < integers.length; ++j) {
for (int j = i; j < integers.length; ++j) {
if (integers[indexMin] > integers[j]) {
indexMin = j;
}
}
// if (indexMin != i) {
int temp = integers[i];
integers[i] = integers[indexMin];
integers[indexMin] = temp;
// }
}
}
＊개선 1: 순회할 때 최소와 최대를 동시에
ㆍ약간의 효율성을 높일 뿐, 2중 반복문이므로 시간복잡도는 여전히 𝑂(𝑛2)
public void selectionSortSimultaneous(int[] integers) {
// 양 끝에 동시에 자리 잡으므로
// 시작 위치를 n-1 까지가 아닌,
// 절반(총 요소 수 짝수) 혹은 절반+1(총 요소 수 홀수) 까지로 줄일 수 있다.
// 약간의 효율성을 높일 뿐, 시간복잡도는 여전히 𝑂(𝑛^2)이다.
for (int i = 0; i <= integers.length / 2; ++i) {
int indexMin = i;
int indexMax = integers.length - 1 - i;
// 확정된 양 끝이 한 칸씩 줄어든다.
for (int j = i; j < integers.length - i; ++j) {
if (integers[indexMin] > integers[j]) {
indexMin = j;
}
if (integers[indexMax] < integers[j]) {
indexMax = j;
}
}
if (indexMin != i) {
int temp = integers[i];
integers[i] = integers[indexMin];
integers[indexMin] = temp;
// 만약 최솟값이 자리를 잡았는데(위 if (indexMin != i) 반복문이 실행된 지금),
// 이번 최솟값 위치(i)의 값이 최댓값이었다면, 바뀐 index(최댓값이 옮겨진)로 indexMax를 갱신해준다.
if (indexMax == i) {
indexMax = indexMin;
}
}
if (indexMax != integers.length - 1 - i) {
int temp = integers[integers.length - 1 - i];
integers[integers.length - 1 - i] = integers[indexMax];
integers[indexMax] = temp;
}
}
}
＊개선 2: 같은 최솟값은 한꺼번에
ㆍ약간의 효율성을 높일 뿐, 2중 반복문이므로 시간복잡도는 여전히 𝑂(𝑛2)
ㆍ같은 값들을 한꺼번에 처리하기 위해 기억해두는 동작으로 인해 더 느려질 수도 있다...
총 요소 수와 같은 칸의 배열을 만들어두면 공간복잡도가 𝑂(1)에서 𝑂(𝑁)으로 증가하고,
힙 영역을 사용하면 메모리 할당/해제로 더 느려진다.
ㆁ삽입 정렬 (Insertion Sort)
ㆍhttps://en.wikipedia.org/wiki/Insertion_sort
ㆍhttps://ko.wikipedia.org/wiki/삽입_정렬
ㆍhttps://namu.wiki/w/정렬 알고리즘?from=삽입 정렬#s-2.1.3
ㆍ시간 복잡도: 𝑂(𝑛2)
ㆍ공간 복잡도: 𝑂(1)
ㆍ안정성: 보장 됨 (O)
public void insertionSort(int[] integers) {
// for (int i = 1; i < integers.length; ++i) {
for (int i = 0; i < integers.length; ++i) {
int index = i;
while (true) {
if (index == 0) {
break;
}
if (integers[index] < integers[index - 1]) {
int temp = integers[index - 1];
integers[index - 1] = integers[index];
integers[index] = temp;
--index;
} else {
break;
}
}
}
}
ㆁ퀵 정렬 (Quick Sort)
ㆍhttps://en.wikipedia.org/wiki/Quicksort
ㆍhttps://ko.wikipedia.org/wiki/퀵_정렬
ㆍhttps://namu.wiki/w/정렬 알고리즘?from=퀵 정렬#s-2.2.3
ㆍ시간 복잡도 - 평균: 𝑂(𝑛·log𝑛), 최악: 𝑂(𝑛2)
ㆍ공간 복잡도: 𝑂(log𝑛)
ㆍ안정성: 보장 안 됨 (X)
public void quickSortRecursive(int[] integers) {
quickSortRecursiveCore(integers, 0, integers.length - 1);
}
private void quickSortRecursiveCore(int[] integers, int indexLeft, int indexRight) {
if (indexLeft >= indexRight) {
return;
}
int pivotValue = integers[indexRight];
int indexWillBeFixed = indexLeft;
for (int i = indexLeft; i < indexRight; ++i) {
if (integers[i] < pivotValue) {
// if (indexWillBeFixed != i) {
int temp = integers[i];
integers[i] = integers[indexWillBeFixed];
integers[indexWillBeFixed] = temp;
// }
++indexWillBeFixed;
}
}
// if (indexWillBeFixed != indexRight) {
integers[indexRight] = integers[indexWillBeFixed];
integers[indexWillBeFixed] = pivotValue;
// }
quickSortRecursiveCore(integers, indexLeft, indexWillBeFixed - 1);
quickSortRecursiveCore(integers, indexWillBeFixed + 1, indexRight);
}
ㆁ합병 정렬 (Merge Sort)
ㆍhttps://en.wikipedia.org/wiki/Merge_sort
ㆍhttps://ko.wikipedia.org/wiki/합병_정렬
ㆍhttps://namu.wiki/w/정렬 알고리즘?from=합병 정렬#s-2.2.1
ㆍ시간 복잡도: 𝑂(𝑛·log𝑛)
ㆍ공간 복잡도: 𝑂(𝑛)
ㆍ안정성: 보장 됨 (O)
public void mergeSortRecursive(int[] integers) {
if (integers.length > 1) {
int[] arrayNextLeft = new int[integers.length / 2];
int[] arrayNextRight = new int [integers.length - integers.length / 2];
for (int i = 0; i < integers.length; ++i) {
if (i < arrayNextLeft.length) {
arrayNextLeft[i] = integers[i];
} else {
arrayNextRight[i - arrayNextLeft.length] = integers[i];
}
}
mergeSortRecursiveCore(integers, arrayNextLeft, arrayNextRight);
}
}
private void mergeSortRecursiveCore(final int[] arrayOrigin, final int[] arrayLeft, final int[] arrayRight) {
if (arrayLeft.length > 1) {
int[] arrayNextLeft = new int[arrayLeft.length / 2];
int[] arrayNextRight = new int [arrayLeft.length - arrayLeft.length / 2];
for (int i = 0; i < arrayLeft.length; ++i) {
if (i < arrayNextLeft.length) {
arrayNextLeft[i] = arrayLeft[i];
} else {
arrayNextRight[i - arrayNextLeft.length] = arrayLeft[i];
}
}
mergeSortRecursiveCore(arrayLeft, arrayNextLeft, arrayNextRight);
}
if (arrayRight.length > 1) {
int[] arrayNextLeft = new int[arrayRight.length / 2];
int[] arrayNextRight = new int [arrayRight.length - arrayRight.length / 2];
for (int i = 0; i < arrayRight.length; ++i) {
if (i < arrayNextLeft.length) {
arrayNextLeft[i] = arrayRight[i];
} else {
arrayNextRight[i - arrayNextLeft.length] = arrayRight[i];
}
}
mergeSortRecursiveCore(arrayRight, arrayNextLeft, arrayNextRight);
}
// 재귀 결과로 arrayLeft와 arrayRight는 각각 정렬된 상태
// (각각 아래 정렬을 먼저 적용 받은 상태)
int indexLeft = 0;
int indexRight = 0;
for (int i = 0; i < arrayOrigin.length; ++i) {
if (indexLeft >= arrayLeft.length) {
arrayOrigin[i] = arrayRight[indexRight++];
} else if (indexRight >= arrayRight.length) {
arrayOrigin[i] = arrayLeft[indexLeft++];
} else {
if (arrayLeft[indexLeft] <= arrayRight[indexRight]) {
arrayOrigin[i] = arrayLeft[indexLeft++];
} else {
arrayOrigin[i] = arrayRight[indexRight++];
}
}
}
}
ㆁ힙 정렬 (Heap Sort)
ㆍhttps://en.wikipedia.org/wiki/Heapsort
ㆍhttps://ko.wikipedia.org/wiki/힙_정렬
ㆍhttps://namu.wiki/w/정렬 알고리즘?from=힙 정렬#s-2.2.2
ㆍ시간 복잡도: 𝑂(𝑛·log𝑛)
ㆍ공간 복잡도: 𝑂(1)
ㆍ안정성: 보장 안 됨 (X)
class Node {
public Node(int data) {
this.data = data;
}
private int data;
private Node parent;
private Node leftChild;
private Node rightChild;
public void changeNodeData(Node other) {
int temp = this.data;
this.data = other.data;
other.data = temp;
}
}
class Heap {
private Node rootNode;
private void addNode(Node node) {
if (rootNode == null) {
rootNode = node;
} else {
Node parent = getNodeToAdoptNext(rootNode);
if (parent.leftChild == null) {
parent.leftChild = node;
} else {
parent.rightChild = node;
}
node.parent = parent;
sortBranchFromChild(node);
}
}
private void setNodesFromArrays(int[] integers) {
rootNode = null;
for (int i = 0; i < integers.length; ++i) {
addNode(new Node(integers[i]));
}
}
private void sortBranchFromChild(Node node) {
if (node.parent == null) {
return;
}
if (node.parent.data < node.data) {
node.changeNodeData(node.parent);
sortBranchFromChild(node.parent);
}
}
private int popMax() {
int result = rootNode.data;
Node endNode = getEndNode(rootNode);
if (endNode == rootNode) {
rootNode = null;
} else {
Node endsParent = endNode.parent;
if (endsParent.leftChild == endNode) {
endsParent.leftChild = null;
} else {
endsParent.rightChild = null;
}
endNode.parent = null;
endNode.changeNodeData(rootNode);
sortHeapFromParent(rootNode);
}
return result;
}
private void sortHeapFromParent(Node parentNode) {
if (parentNode.leftChild == null && parentNode.rightChild == null) {
return;
} else if (parentNode.leftChild != null && parentNode.rightChild != null) {
if (parentNode.data < parentNode.leftChild.data && parentNode.data < parentNode.rightChild.data) {
if (parentNode.leftChild.data == parentNode.rightChild.data) {
parentNode.changeNodeData(parentNode.leftChild);
sortHeapFromParent(parentNode.leftChild);
} else if (parentNode.leftChild.data > parentNode.rightChild.data) {
parentNode.changeNodeData(parentNode.leftChild);
sortHeapFromParent(parentNode.leftChild);
} else {
parentNode.changeNodeData(parentNode.rightChild);
sortHeapFromParent(parentNode.rightChild);
}
} else if (parentNode.data < parentNode.leftChild.data) {
parentNode.changeNodeData(parentNode.leftChild);
sortHeapFromParent(parentNode.leftChild);
} else if (parentNode.data < parentNode.rightChild.data) {
parentNode.changeNodeData(parentNode.rightChild);
sortHeapFromParent(parentNode.rightChild);
}
} else if (parentNode.leftChild != null) {
if (parentNode.data < parentNode.leftChild.data) {
parentNode.changeNodeData(parentNode.leftChild);
sortHeapFromParent(parentNode.leftChild);
}
} else {
if (parentNode.data < parentNode.rightChild.data) {
parentNode.changeNodeData(parentNode.rightChild);
sortHeapFromParent(parentNode.rightChild);
}
}
}
private Node getEndNode(Node parentNode) {
if (parentNode.leftChild == null && parentNode.rightChild == null) {
return parentNode;
} else if (parentNode.leftChild != null && parentNode.rightChild != null) {
Node leftEnd = getEndNode(parentNode.leftChild);
Node rightEnd = getEndNode(parentNode.rightChild);
Node leftParent = leftEnd.parent;
int leftDepth = 1;
while (leftParent.parent != null) {
leftParent = leftParent.parent;
++leftDepth;
}
Node rightParent = rightEnd.parent;
int rightDepth = 1;
while (rightParent.parent != null) {
rightParent = rightParent.parent;
++rightDepth;
}
if (leftDepth == rightDepth) {
return rightEnd;
} else if (leftDepth < rightDepth) {
return rightEnd;
} else {
return leftEnd;
}
} else if (parentNode.leftChild != null) {
return getEndNode(parentNode.leftChild);
} else {
return getEndNode(parentNode.rightChild);
}
}
private Node getNodeToAdoptNext(Node parentNode){
if (parentNode.leftChild != null && parentNode.rightChild != null) {
Node leftEnd = getNodeToAdoptNext(parentNode.leftChild);
Node rightEnd = getNodeToAdoptNext(parentNode.rightChild);
Node leftParent = leftEnd.parent;
int leftDepth = 1;
while (leftParent.parent != null) {
leftParent = leftParent.parent;
++leftDepth;
}
Node rightParent = rightEnd.parent;
int rightDepth = 1;
while (rightParent.parent != null) {
rightParent = rightParent.parent;
++rightDepth;
}
if (leftDepth == rightDepth) {
return leftEnd;
} else if (leftDepth < rightDepth) {
return leftEnd;
} else {
return rightEnd;
}
} else {
return parentNode;
}
}
}
public void heapSort(int[] integers) {
Heap heap = new Heap();
heap.setNodesFromArrays(integers);
for (int i = integers.length - 1; i >= 0; --i) {
integers[i] = heap.popMax();
}
}
잘못된 정보가 있다면, 꼭 댓글로 알려주세요(비로그인 익명도 가능).
여러분의 피드백이 저와 방문자 모두를 올바른 정보로 인도할 수 있습니다.
감사합니다. -
후원해주실 분은 여기로→