Node Class를 이용한 Heap 구현

문제는 다음과 같다.

Heap 구현 방법을 대략적으로 정리해 보면

  1. Node.h 와 Node.cpp를 만들어 Frequency와 Data를 갖는 Node Class를 만든다.
  2. Heap.h 와 Heap.cpp를 만들어 여러 Node 포인터 변수를 가지는 mean Heap을 만든다.
  3. main.cpp에서 Heap을 만들고 push, pop을 통해 올바르게 Heap을 구현했는지 확인한다.

그래서 먼저 구현에 필요한 변수와 메소드를 정의하는 2개의 헤더 파일을 만들었다.

Node.h

#pragma once

class Node {
    private:
        int m_freq;
        char m_data;

    public:
        Node(int freq, char data);
        ~Node();

        void setFreq(int freq);
        int getFreq() const;
        char getData() const;
};

Heap.h

#pragma once
#include "Node.h"

class Heap {
    private:
        int size;
        Node* heapArray;
 
    public:
        Heap(int initialCapacity);
        ~Heap();

        void push_swap(int curIdx);
        void pop_swap(int curIdx);

        void push(int freq, char data);
        Node* pop();
};

---

그러고 나서 Heap.cpp의 생성자 부분을 구현하던 도중

Heap.cpp > Heap() (수정 전)

Heap::Heap(int initialCapacity){
    assert(initialCapacity>=0);
    size=0;
    heapArray = new Node[initialCapacity+1];
}

다음과 같은 에러가 발생하였다.

Heap.cpp > Heap() (수정 전)

Heap 생성자 수정 전

new 키워드를 사용해서 포인터 배열을 생성하려면, 해당 class의 기본 생성자를 같이 써줘야 했던 것이다.

하지만 나는 Node class에 값을 넣어 생성하려는 게 아닌, heapArray의 크기를 초기화해 주는 기능으로서 사용한 것이기 때문에 생성자를 사용할 수가 없었다.

즉 new 키워드는 포인터 변수를 할당하는 데에는 문제가 없지만, 포인터 배열로 만드는 순간 new 키워드를 사용할 수가 없었다.

해결 방법을 검색하던 중 new와 malloc의 차이를 정리한 글을 발견하게 되었다.

new와 malloc의 차이

원래 알고 있기로 malloc은 C에서 주로 사용하고, C++에서는 new를 이용하여 동적 메모리를 할당해야 한다고 생각하고 있었는데, 그 정확한 차이는 모르고 있어서 이번 기회에 더 알아보게 되었다.

malloc과 new는 대표적으로 다음과 같은 차이점이 있다고 한다.

1. malloc/free는 라이브러리가 제공하는 함수인데 비해 new/delete는 언어가 제공하는 연산자이다.
그래서 new는 별도의 헤더 파일을 포함할 필요 없이 언제든지 사용할 수 있으며 이 연산자를 쓴다고 해서 프로그램이 커지는 것도 아니다. 연산자이기 때문에 사용자 정의 타입에 대해 오버로딩할 수도 있다.

2. malloc은 필요한 메모리양을 바이트 단위로 지정하고 void *를 리턴하므로 sizeof 연산자와 캐스트 연산자의 도움을 받아야 한다. 이에 비해 new는 할당할 타입을 지정하고 해당 타입의 포인터를 리턴하므로 sizeof 연산자와 캐스트 연산자를 쓸 필요가 없다. 

3. malloc은 메모리를 할당하는 것만이 목적이므로 초기값을 줄 수 없지만 new 연산자는 동적으로 생성한 변수의 초기값을 지정할 수 있다.

4.  new 연산자로 객체를 할당할 때 생성자가 자동으로 호출된다.
생성자를 호출한다는 점이 malloc과 new의 가장 큰 차이점이며 C++에서 별도의 할당 연산자가 추가된 이유이다. 마찬가지로 delete로 객체를 삭제할 때는 파괴자라는 특별한 함수가 자동으로 호출된다.
 
5. malloc/free 함수로 할당한 메모리는  realloc으로 크기를 바꿔 재할당 할 수 있지만 new에는 이에 대응하는 기능이 없어 새로 할당하여 복사하고 원래 메모리를 해제하는 과정을 직접 해야 한다. 그래서 재할당할 때마다 매번 번지가 바뀌며 심지어 축소할 때도 번지가 바뀐다.
 

여기서 가장 큰 차이점은 new 연산자는 생성자/소멸자를 호출한다는 점이다. 그리고 그 점을 활용하여 이 에러를 해결할 수 있었다.

Heap.cpp > Heap() (수정 후)

Heap::Heap(int initialCapacity){
    assert(initialCapacity>=0);
    size=0;
    heapArray = (Node*)malloc(sizeof(Node)* (initialCapacity+1));
}

 

---

 

Heap의 동작 원리나 구현 방식은 이미 머릿속에 있었기 때문에 코드로 바로 작성할 수 있었다.

우선 Node Class 구현은 어렵지 않다.

m_freq와 m_data 2개의 멤버 변수를 가지고 있으며, setFreq(), getReq(), getData() 총 3개의 메소드를 가지고 있다. 따라서 다음과 같이 Node.cpp를 구현할 수 있다.

Node.cpp

#include "Node.h"

Node::Node(int freq, char data){
    m_freq = freq;
    m_data = data;
}
Node::~Node(){
}
void Node::setFreq(int freq){
    m_freq = freq;
}
int Node::getFreq() const{
    return m_freq;
}
char Node::getData() const{
    return m_data;
}

여기서 눈여겨볼 점이 있는데, Destructor에 아무것도 작성하지 않는다는 점이다.

Node Class 자체 내부에는 별도의 메모리를 할당하는 변수가 없기 때문에 Destructor에서 별도로 해 줄 작업이 없다.

다만 나중에 main.cpp 파일에서 Node형 포인터 변수를 delete해주는 이유는 Heap의 각각의 요소인 Node가 포인터 변수로서 동작하기 때문이다.

---

Heap.cpp > push 관련 메소드

void Heap::push_swap(int curIdx) {
    if(curIdx == 1) return;

    int parentIdx = curIdx / 2;
    if(heapArray[parentIdx].getFreq() > heapArray[curIdx].getFreq()) {
        Node tmpNode = heapArray[parentIdx];
        heapArray[parentIdx] = heapArray[curIdx];
        heapArray[curIdx] = tmpNode;
        push_swap(curIdx / 2);
    }
}

void Heap::push(int freq, char data){
    Node *newNode = new Node(freq, data);
    heapArray[++size] = *newNode;
    push_swap(size);
}

Heap 자료구조에서 push는 다음과 같은 순서로 이루어진다. (min Heap의 경우)

1. 새로운 Node를 Complete Binaray Tree 기준 가장 마지막 위치에 삽입한다.
2. 삽입한 노드가 부모 노드보다 더 작다면 두 노드의 위치를 바꾼다.
3. 2번 과정을 삽입 노드가 부모 노드보다 더 커질 때까지 반복한다.

Heap을 배열로 표현하게 되면 어떤 노드의 부모 노드는 (currentNodeIndex * 2) 로 나타낼 수 있기 때문에 쉽게 구현할 수 있었다.

삽입을 구현하면서 주의할 점은 한 가지 정도가 있었는데

바로 새로운 노드를 만들어 삽입할 때에는 Node 포인터 변수로 만들어야 하고, 두 노드의 인덱스를 swap 할 때에는 그냥 Node 변수로 만들어야 한다는 점이다.

처참한 디버깅의 현장

---

Heap.cpp > pop 관련 메소드

void Heap::pop_swap(int curIdx){
    int leftIdx, rightIdx, childIdx;
    leftIdx = (curIdx*2 <= size ? curIdx*2 : -1);
    rightIdx = (curIdx*2+1 <= size ? curIdx*2+1 : -1);

    if(leftIdx == -1 && rightIdx == -1) 
        childIdx = -1;
    else if(leftIdx != -1 && rightIdx == -1)
        childIdx = leftIdx;
    else 
        childIdx = (heapArray[leftIdx].getFreq() < heapArray[rightIdx].getFreq() ? leftIdx : rightIdx);

    if(childIdx == -1) return;

    if(heapArray[childIdx].getFreq() < heapArray[curIdx].getFreq()) {
        Node tmpNode = heapArray[childIdx];
        heapArray[childIdx] = heapArray[curIdx];
        heapArray[curIdx] = tmpNode;
        pop_swap(childIdx);
    }
}

Node* Heap::pop(){
    Node *minNode = new Node(heapArray[1].getFreq(), heapArray[1].getData());
    heapArray[1] = heapArray[size--];
    pop_swap(1);
    return minNode; 
}

pop 알고리즘은 조금 더 복잡하다면 복잡하다고 할 수 있다.

1. 최상단 노드(Minimum Node = root Node)를 pop 한다.
2. Complete Binary Tree 기준 가장 마지막 위치의 노드를 최상단 노드로 옮긴다.
3. heapify 알고리즘을 이용하여 Heap 자료구조를 유지한다.

* heapify 알고리즘
1. 어떤 노드의 Left Child와 Right Child가 있는지 검사 한 뒤 3가지의 경우의 수를 확인한다.
    1-1. Left Child 와 Right Child 둘 다 없는 경우 => 해당 노드는 Leaf Node이므로 heapify 종료
    1-2. Left Child 만 있는 경우 => Left child와 해당 노드를 비교하여 해당 노드가 더 크다면 swap
    1-2. Left Child와 Right Child 둘 다 있는 경우 => 두 노드를 비교하여 더 작은 노드를 저장하고,
해당 노드와 비교하여 해당  노드가 더 크다면 swap
2. 마찬가지로 계속 반복하여 해당 노드가 자신 노드보다 커질 때까지 반복한다.

pop 알고리즘을 구현하면서도 한 가지 에러를 마주치게 되었다.

가장 먼저 pop 부분을 구현하려 했을 때 다음과 같이 코드를 작성했었다.

Node* Heap::pop(){
    Node *minNode = &heapArray[1];
    heapArray[1] = heapArray[size--];
    pop_swap(1);
    return minNode; 
}

하지만 다음과 같은 에러 메시지를 마주치게 되었다.

main(33254,0x1fa762500) malloc: *** error for object 0x132606828: pointer being freed was not allocated main(33254,0x1fa762500) malloc: *** set a breakpoint in malloc_error_break to debug

구글링 해보니 해제하려는 변수의 메모리에 아무것도 할당되어 있지 않아 생기는 에러인 것 같았다.

실제로 console을 찍어보며 디버깅해 보니 main.cpp의 delete 부분에서 프로그램이 멈추는 것을 확인할 수 있었다.

그리고 한참을 해결하지 못하던 중에 현업 개발자에게 도움을 요청했지만

꼭 물어보고 나서 해결됨

Node *minNode = &heapArray[1];

부분에서 main.cpp 해서 delete 하게 되는 minNode에 메모리를 할당하는 것이 아닌 단순히 주소값을 대입하기 때문인가..?라는 생각이 들었고

저 부분을 단순히 heapArray[1] (Minimum Node, Root Node)의 주소를 대입하는게 아니라

해당 주소의 Frequency와 Data를 Get하고 새로운 메모리를 할당하여 대입하면 해결될 거라는 생각이 들어서 해봤더니 결과는 성공적이었다.

Node *minNode = new Node(heapArray [1]. getFreq(), heapArray [1]. getData());

그렇게 최종적으로 Heap 알고리즘을 구현할 수 있었다.

 

---

 

☀︎ 참고글 ☀︎

https://seulgit.tistory.com/81 : malloc과 new 비교

https://skmagic.tistory.com/111 : malloc과 new의 구체적인 차이점