힙 (Heap)

<배열 사용 버전>

최소힙, 루트 노드를 0번으로 지정.

(1번으로 지정하는 게 더 편리하긴 함)

int heap[100];
int heapSize = 0;

void init(){
    heapSize = 0;
}

int push(int value){
    if (heapSize == 100) return 0; // 최대 사이즈를 넘어가면 나가리
    heap[heapSize] = value; // 마지막 노드에 값 추가
    // 마지막 노드에 추가한 값을 올바른 위치로 옮김
    int current = heapSize; // 현재 위치 저장
    while(current > 0 && heap[(current - 1) / 2] > heap[current]){ // 최소힙인데 부모 > 자식이면 안 되니까 바꿔주기
        // 부모랑 자식 swap
        int tmp = heap[(current - 1) / 2];
        heap[(current - 1) / 2] = heap[current];
        heap[current] = tmp;
        current = (current - 1) / 2; // current는 부모
    }
    ++heapSize; // 다음 노드
    return 1; // push 성공
}

int pop(){ // top(루트 노드) 뺌
    if (heapSize == 0) return -1; // empty인 경우
    int value = heap[0]; // 뻴 루트 노드
    --heapSize; // heap 사이즈 줄여주기
    heap[0] = heap[heapSize]; // 루트에 마지막 노드 저장

    int current = 0; // 현재 노드 = 루트 노드
    while(current * 2 + 1 < heapSize){
        int child, left = current * 2 + 1, right = left + 1;
        if (right == heapSize) child = left;  // 오른쪽 자식이 없는 경우 child는 무조건 왼쪽
        else child = left <= right ? left : right; //  더 작은 놈을 올려야 함
        if (heap[current] <= heap[child]) break; // 부모 <= 자식이면 더 이상 바꿔줄 필요가 없으므로 나옴

        int tmp = heap[current];
        heap[current] = heap[child];
        heap[child] = tmp;
        current = child; // current는 자식
    }
    return value; // 뺀 노드 리턴
}

 

<연결 리스트 사용 버전>

최소힙, 루트 노드를 1번으로 지정.

배열을 사용하게 되면 실행 속도는 빠르지만

메모리가 커질 땐 좋은 방법이 아닐 수 있다.

ex) 1000명의 user가 있고, user들에게 총 1000000개의 데이터를 할당하려 할 때,

1명에게 1000000개의 데이터가 몰릴 수도 있으니까

user들에게 각각 1000000개씩 데이터를 할당해야 하는데

그렇게 되면 메모리가 어마무시하게 커지기 때문에 배열로 구현하기 어렵다.

그래서 이런 경우에는 속도에서 손해를 좀 보더라도

연결 리스트로 구현해야 한다.

(코드가 예쁘진 않다^^..)

struct Node{
    int val;
    Node* parent;
    Node* child[2];
    Node(){}
    Node(int val){
        this->val = val;
        parent = child[0] = child[1] = nullptr;
    }
} memPool[1000001];
int memPoolCnt, heapSize;
Node* root;  // 항상 루트 노드를 가리킴
Node* findNode(int cur){
    if (cur == 1) return root;
    return findNode(cur / 2)->child[cur % 2]; // cur노드가 부모의 왼쪽이었는지 오른쪽이었는지 찾아서 리턴
}
int push(int val) {
    if (memPoolCnt > 1000000) return 0;
    memPool[memPoolCnt] = {val};
    Node* newNode = &memPool[memPoolCnt++];
    if(heapSize++ == 0) root = newNode;
    else{
        Node* parent = findNode(heapSize / 2); // heapSize 늘려서 새 노드 넣을 위치 확보 후 그의 부모 찾음
        newNode->parent = parent;
        parent->child[heapSize % 2] = newNode;  // 맨 마지막 노드에 새 노드 넣기

        Node* current = newNode;
        whlie(current != root && current->parent->val >= current->val){ // 최소힙인데 부모 > 자식 이면 안 되니까 바꿔주기
            int tmp = current->val;
            current->val = current->parent->val;
            current->parent->val = tmp;
            current = current->parent;
        }
    }
    return 1;
}

int pop(){
    if (heapSize == 0) return -1;
    int val = root->val;
    if(heapSize == 1){
        --heapSize;
        root = nullptr;
        return val;
    }
    Node* current = findNode(heapSize); // 맨 마지막 노드
    root->val = current->val;
    current->parent->child[heapSize % 2] = nullptr; // 마지막 노드 연결 제거
    --heapSize; // 힙 사이즈 줄임
    current = root;  // 루트부터 내려가면서 재정렬
    while (current->child[0] != nullptr) {
        int childIdx = 0;
        if (current->child[1] != nullptr) childIdx = current->child[0] <= current->child[1] ? 0 : 1;
        if (current->parent <= current->child[childIdx]) break; // 부모 <= 자식 이면 나옴
        int tmp = current->child[childIdx]->val;
        current->child[childIdx]->val = current->parent->val;
        current->parent->val = tmp;
        current = current->child[childIdx];
    }
    return val;
}
int main() { return 0; }