[C,C++] prioritiy queue with heap

0908

포인터

1. '포인터도 변수다'

         포인터는 값(value)의 주소를 갖고 있는 변수이다.

        int*  : 인트형 포인터 변수

2. &, * 는 연산자다.

       & :  뒤에있는 변수를 값( value ) 로 인식. 해당 값이 있는 포인터(즉 주소)를 알려준다. (return value : pointer)

       *  :  뒤에 있는 변수를 포인터로 인식. 해당 포인터의 연결된 값을 알려준다. (return value : value)

 

Heap

완전 2진 tree. 부모노드 *2 -> 자식노드

 

Priority Queue with heap

무조건 부모노드가 자식노드보다 높은 우선순위를 갖도록 해야한다.

1. add value

 1) heap의 제일 마지막 노드에 놓는다.

 2) 정해진 priority에 맞게 위로 올라가면서 점검한다.(upHeapify)

      2-1) 부모노드보다 priority가 높으면, 자리 스위치

      2-2) 까먹지 말자 initialize (여기선, 가장 root node만 처리하면 되겠네)

 

2. pop value

  1) 첫번째 노드의 값과 마지막 노드의 값을 바꾼다. (그리고 마지막 노드의 값을 pop)

  2) 정해진 priority에 맞게 아래로 내려가면서 점검한다. (downHeapify)

       2-1) 자식노드보다 priority가 낮으면, 자리 스위치

           2-1-1) 자식이 2개잖아..! 그럼 일단 자식들끼리 먼저 비교. 자식들중에서 priority높은 것과만 비교하면 되겠구만.

           2-1-2) 자식이 1개거나,, 자식이 없거나 하면 처리해줘야겠군.

       2-2) 까먹지말자 initialize (여기선... 자식이 없는 경우만 처리.. 이미 해버렸군)

#include <stdio.h>

int h[1001];//init start index with 1
int cnt = 0;

bool compare(int x, int y){
    return x > y; // make priority
}

//pointer change
bool swap(int* i, int* j){//index
    int temp = *i;
    *i = *j;
    *j = temp;
}

void upHeapify(int index){
    //initialize
    if (index == 1){
        return; //do nothing
    }
    //compare with parent node
    if (compare(h[index],h[index/2])){
        swap(&h[index],&h[index/2]);
        upHeapify(index/2); //compare with upper parent
    }
}

void insert (int data){
    h[cnt++] = data; //add value to last array
    upHeapify(cnt);
}

void downHeapify(int index){
    int child;
    //check child
    if (index * 2 > cnt){
        //there is no children
        return;
    }
    //2child -> find priority
    if (index * 2 + 1 <= cnt){
        if (compare(h[index*2],h[index*2+1])){
            child = index * 2;
        }
        else{
            child = index * 2 + 1 ;
        }
    }
    //1child
    else{
        child = index * 2;
    }

    if (compare(h[child],h[index])){//no heap
        swap(&h[index],&h[child]);
        downHeapify(child);
    }

}

void pop (){
    //swap value
    swap(h[1],h[cnt]);
    cnt--;

}

void top(void){
    return h[1];
}