Heap sort utilizando estrutura de árvore binária ao invés de um vetor

Programação C e C++
,
#1

O problema é o seguinte:

Reescreva o algoritmo HeapSort usando uma estrutura de árvore binária, ao invés de um vetor.

Eu produzi o seguinte código ao tentar encontrar uma solução para o problema:

#include <iostream>
#include <ctime>
#include <cstdlib>

using namespace std;

typedef struct node{
    int value;
    struct node* father;
    struct node* lSon;
    struct node* rSon;
} node;

node* treeCreate(int N);
void preOrder(node* root);
void treeDelete(node* root);
void heapSort(node* root);

int main(){
    node* root = treeCreate(7);
    preOrder(root);
    heapSort(root);
    preOrder(root);
    treeDelete(root);
    return 0;
}

node* treeCreate(int N){
    if(N <= 0){
        return NULL;
    }
    node** nodes = new node*[N + 1];
    nodes[0] = NULL;
    srand((unsigned)time(0));
    for(int i = 1; i <= N; i++){
        nodes[i] = new node;
        nodes[i]->value = rand()%(N * 10);
        nodes[i]->father = nodes[i/2];
        nodes[i]->lSon = NULL;
        nodes[i]->rSon = NULL;
        if(i == 1){
            continue;
        }
        if(i % 2 == 0){
            nodes[i]->father->lSon = nodes[i];
        }else{
            nodes[i]->father->rSon = nodes[i];
        }
    }
    node* root = nodes[1];
    delete[] nodes;
    return root;
}

void preOrder(node* root){
    if(root == NULL){
        return;
    }
    cout << root->value << " ";
    preOrder(root->lSon);
    preOrder(root->rSon);
}

void treeDelete(node* root){
    if(root == NULL){
        return;
    }
    treeDelete(root->lSon);
    root->lSon = NULL;
    treeDelete(root->rSon);
    root->rSon = NULL;
    delete root;
}

node* findLastSon(node* root){
    if(root->lSon == NULL){
        return root;
    }else if(root->rSon == NULL){
        return root->lSon;
    }else{
        findLastSon(root->rSon);
    }
}

void maxHeapfy(node* root){
    if(root == NULL){
        return;
    }
    node* bigger;
    if(root->lSon->value > root->value){
        bigger = root->lSon;
    }else if(root->rSon->value > root->value){
        bigger = root->rSon;
    }else{
        bigger = root;
    }
    if(bigger != root){
        int aux = bigger->value;
        bigger->value = root->value;
        root->value = aux;
        maxHeapfy(bigger);
    }
}

node* findLastFather(node* root){
    if(root->lSon == NULL){
        return root->father;
    }else if(root->rSon == NULL){
        return root;
    }else{
        findLastFather(root->rSon);
    }
}

void buildMaxHeap(node* root){
    node* lFather = findLastFather(root);
    while(lFather != root){
        maxHeapfy(lFather);
        if(lFather == lFather->father->rSon){
            lFather = lFather->father->lSon;
        }else{
            lFather = lFather->father;
        }
    }
    maxHeapfy(root);
}

void heapSort(node* root){
    buildMaxHeap(root);
    node* lastSon = findLastSon(root);
    while(lastSon != root){
        int aux = lastSon->value;
        lastSon->value = root->value;
        root->value = aux;
        maxHeapfy(root);
        if(lastSon == lastSon->father->rSon){
            lastSon = lastSon->father->lSon;
        }else{
            lastSon = lastSon->father;
        }
    }
}

Quando eu executo o código, a primeira chamada da função preOrder é executada corretamente, mas em seguida o programa trava. Acredito que eu esteja fazendo algum tipo de loop infinito com a recurção da função maxHeapfy.

Simplesmente não consgigo encontrar uma solução para o problema, e sempre que eu pesquiso na internet, só encontro a solução clássica, utilizando um vetor pra representar o heap.

Alguém pode me dar alguma orientação de como proceder na resolução deste problema?

Desde já, agradeço.

#2

Cara ou debuga, andando passo a passo*

Ou bota uns prints / couts na entrada e saída de cada método, pra fazer tracing, e saber o que esta acontecendo.

Exemplo de macro pra fazer tracing:

#define TRACE_ENTER()    do { printf(">>> Entrou em %s\n", __func__); } while(0);
#define TRACE_EXIT()     do { printf("<<< Saiu de %s\n", __func__); } while(0);
#define TRACE_MSG(m)     do { printf("!!! Mensagem em %s: %s\n", __func__, m); } while(0);

...

void minha_funcao_que_quero_debugar() {
    TRACE_ENTER();
    fazer_coisas_complicadas();
    TRACE_MSG("Fez coisas complicadas");
    fazer_mais_coisas();
    TRACE_EXIT();
}

Isto vai imprimir:

>>> Entrou em minha_funcao_que_quero_debugar
!!! Mensagem em minha_funcao_que_quero_debugar: Fez coisas complicadas
<<< Saiu de minha_funcao_que_quero_debugar

*uma das frustrações de curso de programação é que até tem uns cursos bons que ensinam a provar o algoritmo formalmente, criar testes, mas o povo não ensina a depurar algoritmos no código.

1 curtida