[Algorithm] Max heapify 구현과 이론

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을 만들어 갈수 있기 때문이다.

 

728x90

 

구현

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