Max heapify
최대힙에 대해서 알아보고 구현까지 해보자
힙이란?
완전이진트리의 한 종류이다.
힙의조건
heap property를 만족해야 된다.
Heap property
1.Max heap property
부모는 자식보다 크거나 같다.
2.Min heap property
부모는 자식보다 작거나 같다.
힙의구조
구현방법
1. Tree의 index 표현
root = i;
Left child = i * 2
Right child = i * 2 +1
2. Swap 방법
자식노드가 부모노드 보다 크면 자리를 변경한다.
3. 반복하면서 Max heap을 만들어 간다.
4. 실제로 구현할 때는 맨 마지막 노드 즉 index 7번의 부모노드부터 선택하여 반복 정렬해간다.
그래야 순차적으로 root들을 기준으로 max heap을 만들어 갈수 있기 때문이다.
구현
c++
#include<iostream>
#include<algorithm>
using namespace std;
void swap(int *array, int idx1, int idx2)
{
int tmp = array[idx1];
array[idx1] = array[idx2];
array[idx2] = tmp;
}
void maxHeapify(int* array, int idx, int size)
{
int leftChild = idx * 2 + 1;
int rightChild = idx * 2 + 2;
int updateIndex = idx;
if (leftChild < size && array[updateIndex] < array[leftChild]) {
updateIndex = leftChild;
}
if (rightChild < size && array[updateIndex] < array[rightChild]) {
updateIndex = rightChild;
}
if (idx != updateIndex) {
swap(array, idx, updateIndex);
maxHeapify(array, updateIndex, size);
}
}
int main() {
int array[] = { 5,3,17,10,84,19,6,22,9};
int size = 9;
for(int i = size/2-1; i >= 0; i--) {
maxHeapify(array, i, size);
}
for (int i = size - 1; i > 0; i--) {
swap(array, 0, i);
maxHeapify(array, 0, i);
}
}
java
public class MaxHeap {
static int heapSize = 0;
static int nodeCount = 0;
public static void swap(int []array, int idx1, int idx2)
{
int tmp = array[idx1];
array[idx1] = array[idx2];
array[idx2] = tmp;
}
public static void maxHeapify(int []array, int idx)
{
int leftChild = idx * 2 + 1;
int rightChild = idx * 2 + 2;
int updateIndex = idx;
if (leftChild < heapSize && array[updateIndex] < array[leftChild]) {
updateIndex = leftChild;
}
if (rightChild < heapSize && array[updateIndex] < array[rightChild]) {
updateIndex = rightChild;
}
if (idx != updateIndex) {
swap(array, idx, updateIndex);
maxHeapify(array, updateIndex);
}
}
public static void insert(int[]heap, int key) {
int i = heapSize++;
nodeCount++;
heap[i] = key;
while (i > 0 && heap[i/2] < heap[i]){
swap(heap, i/2, i);
i = i/2;
}
}
public static void delete(int[]heap, int value) {
int deleteIndex = -1;
for(int i = 0; i <heap.length; i++) {
if(heap[i] == value) {
deleteIndex = i;
}
}
if(deleteIndex == -1) {
return;
}
heap[deleteIndex] = heap[heapSize-1];
heapSize--;
for(int i = heapSize/2; i >= 0; i--) {
maxHeapify(heap, i);
}
}
public static void heapSort(int []heap, int length) {
heapSize = length;
// 힙을 만든다.
for(int i = heapSize/2; i >= 0; i--) {
maxHeapify(heap, i);
}
}
public static void printHeap(int []heap) {
int printSize = heapSize;
for (int i = heapSize - 1; i > 0; i--) {
heapSize--;
swap(heap, 0, i);
maxHeapify(heap, 0);
}
for(int i = 0; i < printSize; i++){
System.out.println(heap[i]);
}
}
public static void main(String[] args) {
int heap[] = new int[1000000];
heap[0] = 3;
heap[1] = 22;
heap[2] = 4;
heap[3] = 55;
heap[4] = 7;
heap[5] = 100;
heap[6] = 2;
heap[7] = 313;
heapSort(heap, 8);
insert(heap,11);
delete(heap,313);
printHeap(heap);
}
}
코드를 구현하는것보다 설명하고 그림을 만드는데 시간이
많이 걸린다. 다른 쉬운 방법이 없을까 고민해보자.
참고사항
java 코드에는 insert 와 delete를 넣어 주었다
1. 물론 배열도 static 으로 구현 하여 쉽고 간결하게 변경할수 있다.
2. arraylist로 쉽게 구현 할 수 있다.
3. 삭제는 직접 구현했다.
ArrayList 구현
그래서 ArrayList 로 구현하였다.
차이점
1. Collections.swap 있기 때문에 swap 함수를 지웠다.
2. ArrayList 로 구현을 해도 maxHeapify를 보면 size를 굳이 넣어 주었다.
이유는 sort를 해주려고 넣어 주었다.
4. delete 삭제 했다. remove를 쓰면되기 때문이다.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
public class MaxHeap {
public static void maxHeapify(ArrayList<Integer> list, int idx, int size)
{
int leftChild = idx * 2 + 1;
int rightChild = idx * 2 + 2;
int updateIndex = idx;
if (leftChild < size && list.get(updateIndex) < list.get(leftChild)) {
updateIndex = leftChild;
}
if (rightChild < size && list.get(updateIndex) < list.get(rightChild)) {
updateIndex = rightChild;
}
if (idx != updateIndex) {
Collections.swap(list, idx, updateIndex);
maxHeapify(list, updateIndex, size);
}
}
public static void insert(ArrayList<Integer> list, int key) {
list.add(key);
int i = list.size()-1;
while (i > 0 && list.get(i/2) < list.get(i)){
Collections.swap(list, i/2, i);
i = i/2;
}
}
public static void delete(ArrayList<Integer> list, int key) {
list.remove(list.size());
}
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
list.add(3);
list.add(22);
list.add(4);
list.add(55);
list.add(7);
list.add(100);
list.add(11);
list.add(313);
list.add(1);
for(int i = list.size()/2-1; i >= 0; i--) {
maxHeapify(list, i, list.size());
}
insert(list, 120);
int range = list.size()-1;
for (int i = list.size() - 1; i > 0; i--) {
Collections.swap(list, 0, i);
maxHeapify(list, 0, range--);
}
for(int i = 0; i < list.size(); i++){
System.out.println(list.get(i));
}
}
}
전체코드
구현:
https://github.com/rnrl1215/algorithm-base/tree/master/src/main/java/algorithm/maxheap
테스트코드:
https://github.com/rnrl1215/algorithm-base/blob/master/src/test/java/MaxHeapTest.java
'Algorithm > 알고리즘 기본' 카테고리의 다른 글
[Algorithm] Binary Search Tree - Insert (0) | 2021.06.08 |
---|---|
[Algorithm] Counting Sort (0) | 2021.05.21 |
[Algorithm] 병합정렬(merger sort) (0) | 2021.04.13 |
[Algorithm] 조합 구현 (0) | 2021.04.11 |
[Algorithm] 순열과 조합 (0) | 2021.04.11 |
댓글