c++

heap sort

hojung 2022. 3. 15.

728x90

1. heap sort

heap sort는 완전 이진 트리의 형태를 만족한다.

완전 이진트리란 tree의 leaf node들의 층수가 모두 같은 트리를 의미한다.

위의 그림에서 볼 수 있듯이 같은 층이 완전히 차기 전까지는 leaf node가 새로운 층으로 내려가지 않는다.

나는 최대 힙을 구현해볼 것이다. 언어는 c++를 사용하였다.

2. 구현을 위해 생각해야 하는 것 1. 노드가 가질 정보

각 노드들은 데이터를 가질 부분, 노드의 왼쪽 아래 층의 인덱스에 대한 정보, 노드의 오른쪽 아래 층의 인덱스에 대한 정보 총 3가지의 정보를 가져야한다.

struct node // 데이터를 입력받을 노드 
{
    int data; // 데이터
    struct node* left; // 왼쪽 노드
    struct node* right;//오른쪽 노드
};

따라서 다음과 같이 node의 struct를 만들어주었다.

3.구현을 위해 생각해야 하는 것 2. 더하는 기능

void addNode(node* tmp1, node* parent, int pos)
{
    int dir = GETBIT(nodes, pos);   //노드들의 개수를 이진수로 변환했을 때 맨끝자리가 1이면 오른쪽 0이면 왼쪽   

    if (pos == 0)//pos값이 없다면 root //
    {
        if (dir) // 만약 비트연산의 결과가 1이라면 오른쪽으로 간다. 
            tmp1->right = current;
        else
            tmp1->left = current;//아니면 왼쪽으로 간다. 

        current->left = 0;
        current->right = 0;

        if (current->data > tmp1->data)//현재 노드의 데이터가 새로운 노드의 데이터보다 크다면 
            swap(&current->data, &tmp1->data);//바꿔준다.
    }

    else
        if (dir==1) // pos값이 존재하고 (층수) 결과가 1이라면 오른쪽 노드로 가서 다시 호출한다. 
            addNode(tmp1->right, tmp1, pos - 1);
        else
            addNode(tmp1->left, tmp1, pos - 1);//아니면 왼쪽노드로 가서 다시 호출한다. 

    if (tmp1->data > parent->data)//만약 새로들어온 data가 부모보다 크다면 바꿔준다. 
        swap(&parent->data, &tmp1->data);
}

완전 이진트리의 형태를 유지해야하므로 끝의 노드에 이미 하나의 child node가 존재할 경우 parent node의 오른쪽으로 아무 child node가 없을 경우 left로 가야한다.

이 때 Bit 연산자를 이용한다. 완전 이진트리를 구현하기 위해서는 노드들의 수에 대한 데이터가 있어야한다.

1층 -1개

2층 - 2개

3층 - 4개

4층 - 8개

하지만 데이터가 추가됨에 따라 우리는 어디 위치에 삽입해야 하는가에 대한 의문점이 들 수 있다.

내가 생각한 방법은 두 가지이다. 한 가지는 전역적으로 마지막 노드의 위치를 포인터 정보로 가지고 있은 후 parents의 자식 수가 1개이면 parents의 오른쪽에 삽입하는 방법이다.

다른 한 가지는 오랜 고민끝에 나온 방법인데 bit 연산자를 이용하는 방법이다. 예를 들면 8번째 노드가 새로 들어온다면 현재 노드의 수 8을 2진수로 변환하면 1000이다. 이는 그림에서 알 수 있듯이 2진수는 앞자리가 무조건 1이므로 2번째부터 확인하면 0 0 0이다. 이 때 0이면 왼쪽 1이면 오른쪽으로 이동하면 된다. 따라서 000은 왼쪽 -> 왼쪽 -> 왼쪽

9번째 노드가 들어가게 되면 2진수로 변환하게 되면 1001이므로 앞에서 2번째부터 0 0 1이므로 왼쪽 왼쪽 오른쪽으로 이동하면 된다.

넣어야하는 위치를 찾고 현재 가리키고 있는 노드의 값이 새로 들어온 노드의 값보다 크다면 둘의 위치를 바꿔준다.

void swap(int* a, int* b) // heap을 구성할 때 부모노드와 자식노드의 값을 비교 후 바꿔주는 함수
{
    *a = *a + *b;
    *b = *a - *b;
    *a = *a - *b;
}

두 번째 위치를 찾는 기능은 다음과 같다.

void preorder(node* tmp) {
    cout << tmp->data <<" ";
    
    if (tmp->left != NULL)
        preorder(tmp->left);
    if (first->right != NULL)
        preorder(tmp->right);
}

코드를 확인해보면 tmp의 left를 확인하여 존재한다면 왼쪽으로 내려가 다시 preorder함수를 호출하여 확인하고 첫번째 노드의 오른쪽이 차있다면 오른쪽으로 내려가서 다시 preorder함수를 호출하는 방식으로 구현하였다, 두 가지 방식 중 하나를 사용하여 구현하면 된다.

4. 구현을 위해 생각해야하는 것 3. sorting

void heapSort(node* tmp)
{
    if (!tmp->right && !tmp->left)//right와 left의 값이 존재하지 않는다면 리턴한다.
        return;

    if (!tmp->right) // tmp의 right값이 존재하지 않는다면
    {
        if (tmp->left->data > tmp->data)//left의값이 현재 포인터저장된 값보다 크다면 바꿔준다.
            swap(&tmp->left->data, &tmp->data);
    }
    else
    {
        if (tmp->right->data > tmp->left->data) // 오른쪽의 데이터가 왼쪽의 데이터보다 클 때
        {
            if (tmp->right->data > tmp->data)//그 큰 오른쪽의 데이터가 부모데이터 보다 크다면
            {
                swap(&tmp->right->data, &tmp->data);//바꿔준다. 
                heapSort(tmp->right);//재귀함수를 통해 모든 트리구조에 적용한다. 
            }
        }
        else
        {
            if (tmp->left->data > tmp->data)//오른쪽 왼쪽 중 왼쪽이 더 크다면 
            {
                swap(&tmp->left->data, &tmp->data);//그리고 그 왼쪽놈이 부모보다 크면 바꿔준다.
                heapSort(tmp->left); // 재귀함수를 통해 모든 트리에 적용시킨다. 
            }
        }
    }
}

5. 구현을 위해 생각해야 하는 것 4. Root를 찾는 것

void getRoot(node* tmp, int pos)
{
    int dir; //비트 값을 저장해줄 정수형 변수

    if (nodes == 1) // 노드가 한개라면 리턴한다.
        return;

    while (pos !=0) //층수가 0이 아니라면
    {
        dir = GETBIT(nodes, pos);//dir변수에 비트연산 값을 집어넣고 

        if (dir==1)//비트연산의 값이 1이라면 오른쪽으로 간다.
            tmp = tmp->right;
        else // 비트연산의 값은 두가지 0,1밖에 없으므로 0이라면 왼쪽으로 간다. 
            tmp = tmp->left;
        pos--; // 층수를 하나씩 줄인다. 
    }

    dir = GETBIT(nodes, pos);

    if (dir==1) // 비트연산의 결과가 1이라면
    {
        first->data = tmp->right->data; // first포인터의 값에 오른쪽 노드의 값을 집어넣는다.
        delete(tmp->right);//tmp->right를 해제한다.
        tmp->right = 0;//다시 초기화 해준다. 
    }
    else
    {
        first->data = tmp->left->data;//비트연산의 결과가 0이라면
        delete(tmp->left); // 왼쪽의 데이터 값을 first에 할당하고 해제한다.
        tmp->left = 0;
    }
}

5. 구현 결과

int main()
{
    int num;
    int  i, j;

    while (1)                                                
    {
        cout << "숫자를 입력하시오" << endl;
        cin >> num;
        current = new node; // 새로생성된 노드가 current
        if (current == 0)
            return 0;
        if (!num) //숫자가 아니라면 흐름을 멈춰라
            break;

        current->data = num;
        nodes++;

        for (i = nodes, j = -1; i; i >>= 1)//층수를 다시 정해준다. 위에서 빠져나가면 원래의 층수가 바뀔 수가 있다. 
        {
            j++;
        };

        if (first == 0)
        {
            first = current;
            first->left = 0;
            first->right = 0;
        }
        else
            addNode(first, first, j - 1);

        cout << " 다음 숫자를 입력하시오" << endl;

    }
    cout << "12171800 심정호" << endl;
    cout << "입력된 노드의 갯수 : " << nodes << endl;

    while (nodes>0) // 노드가 1개 이상 있을 때까지
    {
        printf(" %d -> ", first->data); // 출력한다.                                     

        for (i = nodes, j = -1; i; i >>= 1) // 12171800 심정호
        {
            j++; // 층수를 다시 정해준다. 위에서 부터 빠져나가기 때문에 
        };                                    
        getRoot(first, j - 1);//루트를 빠져나갔으니 1층이 줄어들었다.
        nodes--;//노드의 갯수도 1개 줄어들었다.

        heapSort(first);//빠져나간 후 다시 heapsort를 해준다.
    }

    cout << endl << endl;

    while (1)
    {
        cout << "숫자를 입력하시오" << endl;
        cin >> num;
        current = new node; // 새로생성된 노드가 current
        if (current == 0)
            return 0;
        if (!num) //숫자가 아니라면 흐름을 멈춰라
            break;

        current->data = num;
        nodes++;

        for (i = nodes, j = -1; i; i >>= 1)//층수를 다시 정해준다. 추가 되면 층수가 바뀐다. 
        {
            j++;
        };

        if (first == 0)
        {
            first = current;
            first->left = 0;
            first->right = 0;
        }
        else
            addNode(first, first, j - 1);

        cout << " 다음 숫자를 입력하시오" << endl;

    }
    cout << "12171800 심정호" << endl;
    cout << "입력된 노드의 갯수 : " << nodes << endl;
    preorder(first);

    return 0;
}