Ir ao conteúdo
  • Cadastre-se

C loop nos métodos de uma estrutura heap


Lucas LC
Ir à solução Resolvido por arfneto,

Posts recomendados

Boa noite!

 

Estou fazendo uma fila de prioridade heap, são dois vetores de ponteiros que guardam os elementos inseridos, o método de inserir consegui fazer, mas as outras não consegui muito bem, gostaria de algumas dicas, criei alguns métodos auxiliares para fazer a manutenção da estrutura heap que são: refazHeapMaximo, maxHeapify, aumentarPrioridadeAux, reduzirPrioridadeAux. 

As duas últimas são subir heap, quando a prioridade de um elemento é modificada ele precisa subir na árvore e o descer é quando sua prioridade diminui. A estrutura heap é uma árvore que tem 2 filhos e 1 pai, os dois filhos precisam ser menores que seu pai, por isso essas funções auxiliares.

 

No método aumentar prioridade, reduzir prioridade e remover, está em um loop infinito .

 

Se alguém puder ajudar agradeço. 

 

PFILA criarFila(int max){
  PFILA res = (PFILA) malloc(sizeof(FILADEPRIORIDADE));
  res->maxElementos = max;
  res->arranjo = (PONT*) malloc(sizeof(PONT)*max);
  res->heap = (PONT*) malloc(sizeof(PONT)*max);
  int i;
  for (i=0;i<max;i++) {
    res->arranjo[i] = NULL;
    res->heap[i] = NULL;
  }
  res->elementosNoHeap = 0;
  return res;
}

void exibirLog(PFILA f){
  printf("Log [elementos: %i]\n", f->elementosNoHeap);
  PONT atual;
  int i;
  for (i=0;i<f->elementosNoHeap;i++){
    atual = f->heap[i];
    printf("[%i;%f;%i] ", atual->id, atual->prioridade, atual->posicao);
  }
  printf("\n\n");
}

//Função para trocar a posição dos elementos no heap.
void troca(PONT* a, PONT* b){
PONT t = *a;
*a = *b;
*b = t;

} 

//Posição do filho a esquerda é 2i+1, direita 2i+2, (i-1)/2 é o pai e o 0 é a raiz.
void maxHeapify(PFILA f, PONT atual, int posicao){
int esquerda = 2*posicao+1;
int direita = 2*posicao+2;
int max;

//Propriedade para fazer a manutenção da árvore.
if(esquerda <= f->maxElementos && f->heap[esquerda]->prioridade > f->heap[posicao]->prioridade ){
max = esquerda;
} else {
max = posicao;

}
if(direita <= f->maxElementos && f->heap[direita]->prioridade > f->heap[max]->prioridade){
max = direita;
}
//Fazer a troca do elemento na posição maior.
if(max != posicao){
atual = f->heap[posicao];
f->heap[posicao] = f->heap[max];
f->heap[max] = atual;
maxHeapify(f,atual,max);

           }
return;
}
//Será usado quando removemos um elementos ou reduzimos sua prioridade.
//Árvore binária quase completa em que cada pai é maior ou igual que qualquer de seus filhos.
void refazHeapMaximo(PFILA f, PONT atual){

//Decrescendo para encontrar o maior valor para a manutenção da árvore.
for(int posicao=f->maxElementos/2;posicao>=0;posicao--){
atual = f->heap[posicao]; 
if(atual->prioridade > f->heap[(posicao-1)/2]->prioridade){
maxHeapify(f,atual,posicao);
}
     }
            }

//Sobe no Heap, função interativa 
void aumentarPrioridadeAux(PFILA f, int posicao){
int i = posicao;

//Caso o pai seja menor que seus filhos.
while(i > 0 && f->heap[(i-1)/2]->prioridade < f->heap[i]->prioridade) {
troca(&(f->heap[i]), &(f->heap[(i-1)/2]));
i = (i-1)/2;

  }
     }
     
//Se o atual tiver prioridade maior do que a de seu pai, os dois devem trocar de lugar).
void aumentarPrioridadeAux2(PFILA f, PONT atual){ 
 int i;
 for (i=0;i<f->elementosNoHeap;i++){
 atual = f->heap[i];
 if(atual->prioridade > f->heap[(i-1)/2]->prioridade){ 
 troca(&(atual), &(f->heap[(i-1)/2]));
  } 
       } 
            }

//Descer elemento no Heap
void reduzirPrioridadeAux(PFILA f, int posicao){
int maiorFilho; 

for (posicao=0;posicao<f->elementosNoHeap;posicao++){

if(2*posicao+1 < f->maxElementos){
maiorFilho = 2*posicao+1; 

if(2*posicao+2 < f->maxElementos && (f->heap[2*posicao+1]->prioridade) < (f->heap[2*posicao+2]->prioridade))
maiorFilho = 2*posicao+2; 

if(f->heap[posicao]->prioridade < f->heap[maiorFilho]->prioridade) { 
troca(&(f->heap[posicao]), &(f->heap[maiorFilho]));

}
    }  
        } 
            }
        
void reduzirPrioridadeAux2(PFILA f, PONT atual){
int maiorFilho; 
int i;
for (i=0;i<f->elementosNoHeap;i++){
atual = f->heap[i];

if(2*i+1 < f->maxElementos){
maiorFilho = 2*i+1; 
atual = f->heap[maiorFilho]; 

if(2*i+2 < f->maxElementos && (f->heap[2*i+1]->prioridade) < (f->heap[2*i+2]->prioridade))
maiorFilho = 2*i+2; 
atual = f->heap[maiorFilho]; 

if(f->heap[i]->prioridade < atual->prioridade) { 
troca(&(f->heap[i]), &(atual));

  }
       }
            }
                  }


//Quantidade de elementos no heap. 
int tamanho(PFILA f){
  int tam = 0;
  for(int i=0; i<f->elementosNoHeap;i++){
  tam++;
  }
  return tam;
  }

bool inserirElemento(PFILA f, int id, float prioridade){
  bool res = false;
  ELEMENTO* novoElemento;
  PONT atual;
  int posicao = f->elementosNoHeap; // posição inicial do novo elemento no arranjo chamado heap
  
 //id precisa ser válido e menor que maxElementos na estrutura. 
 if(id < 0 || id >= f->maxElementos) return res;
 //Não incluir elementos repetidos. 
 if(f->arranjo[id] != NULL) return res; 
 atual = f->arranjo[id];
 //Alocar memória para esse elemento. 
 novoElemento = (PONT) malloc(sizeof(ELEMENTO));
//Guarde ele no arranjo de endereços. 
 f->arranjo[id] = novoElemento;
 f->heap[f->elementosNoHeap] = novoElemento; // o novo elemento deve ser inserido na primeira posição livre do arranjo heap
 novoElemento->prioridade = prioridade;
 novoElemento->id = id;
 novoElemento->posicao = f->elementosNoHeap;
 f->elementosNoHeap++; 
 aumentarPrioridadeAux(f,posicao);
  res = true; 
  return res;
}

bool aumentarPrioridade(PFILA f, int id, float novaPrioridade){
  bool res = false;
  PONT atual = f->arranjo[id];
  
 if(f == NULL) return res; 
 if (id < 0) return false; // id negativo
 if (id >= (f->maxElementos)) return res; 
 //Verificar se os elementos do arranjo são válidos ou se tem alguém ou não. 
 if (f->arranjo[id] == NULL) return res;
// Caso a prioridade de um determinado elemento for maior que a variável passado como parâmetro retorne false. 
 if (f->arranjo[id]->prioridade  >= novaPrioridade) return res;
 
 atual->prioridade = novaPrioridade; 
 aumentarPrioridadeAux2(f,atual);
  res = true; 
  return res;
}

bool reduzirPrioridade(PFILA f, int id, float novaPrioridade){
  bool res = false;
  PONT atual = f->arranjo[id];
  
  if(f == NULL) return res; 
  if (id < 0) return false; // id negativo
  if (id >= (f->maxElementos)) return res; // id > maximo
   // Se não tem na fila retorne false. 
  if (f->arranjo[id] == NULL) return res;
  // Caso a prioridade de um determinado elemento for menor que a variável passado como parâmetro retorne false.
  if (f->arranjo[id]->prioridade <= novaPrioridade) return res;
  
  atual->prioridade = novaPrioridade; 
  reduzirPrioridadeAux2(f,atual);
  refazHeapMaximo(f,atual);
  
  res = true; 
  return res;
}

PONT removerElemento(PFILA f){
  PONT res = NULL;
  int id;
  PONT atual = f->arranjo[id];
  int posicao;
  //Verificar se a fila não está vazia. 
  if(f == NULL) return res; 
  if(f->maxElementos == 0) return res; 
  for(posicao = f->elementosNoHeap;posicao >= 0; posicao--)
  //A primeira posição precisa ser excluida. 
  if(posicao == 0)
  atual = f->heap[posicao]; 
  f->elementosNoHeap--; 
  f->heap[posicao] = f->heap[f->elementosNoHeap];
  reduzirPrioridadeAux(f,0);
  //Colocar NULL na posição do arranjo.
  int excluir = atual->id; 
  f->arranjo[excluir] = NULL;

  refazHeapMaximo(f,atual);
  
  res = atual; 
  return res;
}


bool consultarPrioridade(PFILA f, int id, float* resposta){
  bool res = false;
  
  if(f == NULL) return res; 
  if (id < 0) return res; // id negativo
  if (id >= (f->maxElementos)) return res;
  if (f->arranjo[id] == NULL) return res;//Se os elementos da fila for válido.
  
  *resposta = f->arranjo[id]->prioridade;//Colocar na memória o valor da prioridade.
 
  res = true;
  return res;
}

 

Link para o comentário
Compartilhar em outros sites

@Lucas LC poste algo completo, que se possa compilar.

Um link para o projeto no Github é uma opção comum usada em toda parte também. Mas como o projeto é pequeno acho que se postar aqui pode ser útil a outros que chegam por exemplo por uma pesquisa por alguma palavra chave e poderiam ver a discussão toda

  • Curtir 1
Link para o comentário
Compartilhar em outros sites

Ok, vou colocar as informações que estou usando para executar.

 

filaDePrioridade.txt usaFilaDePrioridade.txt

Coloquei as referências usadas e o arquivo de teste. 

 

 

A inserção está correta. 

 

Quando uso a função void aumentarPrioridadeAux2(PFILA f, PONT atual), ela aumenta a prioridade, mas não corretamente, tentei fazer isso usando o PONT atual, o int posicao e até uma função recursiva, fazendo o mesmo trabalho.

 

A mesma coisa acontece em diminuir prioridade. 

Enunciado- heap.docx

  • Curtir 1
Link para o comentário
Compartilhar em outros sites

Se eu fosse você tentaria conversar com o seu professor, porque esse enunciado está muito confuso.

 

É para fazer uma arvore binaria? ou seria um vetor organizado?

O elemento tem a prioridade separada ou ele mesmo é sua própria prioridade?

Fora que não seriam só essas questões, ainda há muito

mais

 

Se fosse eu faria assim, ignorando tudo que não faz sentido no enunciado.

#include <stdio.h>
#include <stdlib.h>


struct pilha_info
{
    unsigned short tamanho;
    unsigned short posicao;
    unsigned short *pilha;
};

void
organizaPilha(struct pilha_info *pilha);

void
iniciaPilha(struct pilha_info *pilha, int tamanho_pilha);

void
apagaPilha(struct pilha_info *pilha);

void
inserePilha(struct pilha_info *pilha, unsigned short valor);

void
mostraPilha(struct pilha_info *pilha);

int main(void)
{
    int d;
    struct pilha_info pilha;
    iniciaPilha(&pilha, 10);
    
    inserePilha(&pilha, 12);
    inserePilha(&pilha, 11);
    inserePilha(&pilha, 1);
    inserePilha(&pilha, 2);
    inserePilha(&pilha, 3);
    inserePilha(&pilha, 4);
    inserePilha(&pilha, 5);
    inserePilha(&pilha, 6);
    inserePilha(&pilha, 7);
    inserePilha(&pilha, 8);
    inserePilha(&pilha, 9);
    inserePilha(&pilha, 10);
    inserePilha(&pilha, 0);
    
    mostraPilha(&pilha);

    apagaPilha(&pilha);
    return(0);
}

void
iniciaPilha(struct pilha_info *pilha, int tamanho_pilha)
{
    /* Cria a pilha */
    pilha->pilha = malloc(sizeof(*pilha->pilha)*tamanho_pilha);
    if (pilha->pilha == NULL) {
        perror("Erro! nao foi possivel reservar memoria!");
        exit(EXIT_FAILURE);
    }

    pilha->tamanho = tamanho_pilha;
    pilha->posicao = 0;
}

void
apagaPilha(struct pilha_info *pilha)
{
    if (pilha->pilha != NULL) {
        free(pilha->pilha);
    }

    pilha->pilha = NULL;
    pilha->tamanho = pilha->posicao = 0;
}

void
organizaPilha(struct pilha_info *pilha)
{
    int contador = 1;
    while (contador) {
        contador = 0;
        for (int tmp = 0; tmp < pilha->posicao-1; tmp++) {
            if (pilha->pilha[tmp] > pilha->pilha[tmp+1]) {
                unsigned short aux = pilha->pilha[tmp];
                pilha->pilha[tmp] = pilha->pilha[tmp+1];
                pilha->pilha[tmp+1] = aux;
                contador++;
            }
        }
    }
}

void
inserePilha(struct pilha_info *pilha, unsigned short valor)
{
    /* Checa se a pilha ainda tem espaço */
    if (pilha->posicao < pilha->tamanho) {
        pilha->pilha[pilha->posicao] = valor;
    } else {
        /* Cria uma pilha maior */
        unsigned short *tmp = malloc(sizeof(*pilha->pilha)*(pilha->posicao+1));
        if (tmp == NULL) {
            perror("Erro! nao foi possivel reservar memoria!");
            exit(EXIT_FAILURE);
        }

        /* Copia a pilha anterior para a nova */
        for (int cont = 0; cont < pilha->tamanho; cont++) {
            tmp[cont] = pilha->pilha[cont];
        }

        /* Insere o novo elemento na pilha */
        tmp[pilha->posicao] = valor;

        /* Apaga a pilha antiga */
        free(pilha->pilha);

        /* Coloca a nova pilha */
        pilha->pilha = tmp;

        /* Coloca o novo tamanho da pilha */
        pilha->tamanho = pilha->posicao+1;
    }
    pilha->posicao++;
    if (pilha->posicao > 1)
        organizaPilha(pilha);
}

void
mostraPilha(struct pilha_info *pilha)
{
    for (int contador = 0; contador < pilha->posicao; contador++)
        printf("\n%hu", pilha->pilha[contador]);
    
    printf("\nPressione enter para continuar.");
    getchar();
}

 

Link para o comentário
Compartilhar em outros sites

@KXSY Um heap não é uma pilha. E pode ser visto como uma árvore binária  balanceada, exceto talvez por um nó.

@Lucas LC Não tive tempo de testar o programa ainda. Consegui compilar, mas está coo sabe cancelando

 

Foi preciso mudar duas coisas do modo como gravei aqui, e acho que devia manter isso:

  • exibirLog() não está declarada  no header
  • removerElemento() começa com
        PONT atual = f->arranjo[id];

    mas de onde vem id?

 

Em relação ao programa, vou repetir o que sempre escrevo: Nunca use typedefs para ponteiros. Só dá confusão. Essas linguagens tem o asterisco precisamente para isso:


Exemplo


Se argv é char** então

  • *argv é char*
  • **argv é char

Não há razão para sequer pensar nisso. É a linguagem. E aí você define um tipo PFILA. Será um ponteiro? Não soma nada. E se todo ponteiro começa por P sempre tem outra ambiguidade: Um ponteiro para um ponteiro começaria por PP? Para que? PONT é um ponteiro para ONT? Acho que deu para entender. Se tem um tipo FILA então para que precisa de PFILA? Ah, PFILA é um ponteiro para FILADEPRIORIDADE. Sério?

Usou isto:

 

typedef struct
{
	int		maxElementos;
	int		elementosNoHeap;
	PONT*	heap;
	PONT*	arranjo;

} FILADEPRIORIDADE, * PFILA;

 

Estaria melhor servido com isto:

 

typedef struct
{
	int		maxElementos;
	int		elementosNoHeap;
	PONT*	heap;
	PONT*	arranjo;

}   FILA;

 

Como seria um ponteiro para fila? Fácil:

 

FILA*

 

e u ponteiro para um ponteiro para FILA?

 

FILA**

 

E nunca teria que saber que *PFILA é FILADEPRIORIDADE

 

Pense nisso... É procurar por problemas. 

 

Sim, a Microsoft tem culpa nisso por ter mantido essas coisas nas API desde os '80. Sim, API não tem plural.

Link para o comentário
Compartilhar em outros sites

2 horas atrás, arfneto disse:

removerElemento() começa com


    PONT atual = f->arranjo[id];

mas de onde vem id?

 

Não foi inicializado no método nessa parte eu já mudei, me equivoquei. 

2 horas atrás, arfneto disse:

Um heap não é uma pilha. E pode ser visto como uma árvore binária  balanceada, exceto talvez por um nó.

Exatamente, ele não entra na definição de pilha e sim de uma árvore quase completa. 

2 horas atrás, arfneto disse:

Não há razão para sequer pensar nisso. É a linguagem. E aí você define um tipo PFILA. Será um ponteiro? Não soma nada. E se todo ponteiro começa por P sempre tem outra ambiguidade: Um ponteiro para um ponteiro começaria por PP? Para que? PONT é um ponteiro para ONT? Acho que deu para entender. Se tem um tipo FILA então para que precisa de PFILA? Ah, PFILA é um ponteiro para FILADEPRIORIDADE. Sério?

Sim, PFILA é um ponteiro da fila de prioridade. E também a estrutura não pode ser mudada.

2 horas atrás, arfneto disse:

Em relação ao programa, vou repetir o que sempre escrevo: Nunca use typedefs para ponteiros. Só dá confusão. Essas linguagens tem o asterisco precisamente para isso:


Exemplo


Se argv é char** então

  • *argv é char*
  • **argv é char

Sim entendi, na verdade eu até me acostumei de usar typedefs como ponteiros. 

Link para o comentário
Compartilhar em outros sites

4 horas atrás, Lucas LC disse:

Sim, PFILA é um ponteiro da fila de prioridade. E também a estrutura não pode ser mudada

 

Não precisa mudar. Apenas não use. O que estou explicando é que na sua estrutura, essa que recebeu e "não pode mudar", PFILA é FILADEPRIORIDADE* e isso é uma bobagem. Dos dois lados. Um tipo de 16 letras é chato mesmo na Islândia, onde as palavras são todas assim.

 

Qual seria a razão para o seu typedef não ser Heap ou MaxHeap? E se tem um 
 

typedef struct
{
	int		maxElementos;
	int		elementosNoHeap;
	PONT*	heap;
	PONT*	arranjo;

} FILADEPRIORIDADE, * PFILA;

 

Não poderia ter algo assim
 

    typedef FILADEPRIORIDADE Heap;

 

E aí a outra estrutura com essa nomenclatura b0b1nh@:
 

typedef struct st-ex
{
	int	id;
	int	posicao;
	float	prioridade;

} ELEMENTO, * PONT;

 

Então você tem que memorizar que PONT é um ponteiro para ELEMENTO. Genial. Acrescentou muito. A linguagem já garante que um ponteiro para ELEMENTO é ELEMENTO*


Veja isso:
 

ELEMENTO*	azul;
PONT		Azul;

 

Se eu posso declarar azul como ELEMENTO* não é muito mais claro que declarar Azul como PONT?? Os dois são a mesma coisa: struct st_ex* só que eu tenho que aprender ou adivinhar que PONT e ELEMENTO* são a mesma coisa.

 

E para piorar em muitos programas ainda se vê o cara declarar algo como PONT* para passar o endereço do ponteiro, como no caso de listas ligadas mal construídas. E aí não se dão ao trabalho de declarar PPONT talvez, para deixar claro que de trata de um ponteiro para um ponteiro para a estrutura original, cujo nome se perdeu. E para saber tem que voltar ao código. Nem todo programa tem 30 linhas e uma ou duas estruturas e isso virando hábito é um inferno. 

Se você convencionar que nenhum typedef é ponteiro, ou a empresa fizer isso, ou o orientador, então nunca terá essa dúvida. 

 

4 horas atrás, Lucas LC disse:

Sim entendi, na verdade eu até me acostumei de usar typedefs como ponteiros

 

Não me leve a mal, mas estou tentando mostrar que não faz sentido. Um ponteiro é o tipo com um asterisco depois. Garantido. 

ELEMENTO

 

Em geral há décadas se reserva os nomes com todas as letras em maiúsculas para constantes, #define como INT_MAX ou todas as constantes em limits.h. Sugiro manter a convenção, porque não pode mudar o que já está escrito e nos headers do windows e do Unix as constantes estão sempre assim.

 

Faça como em java e como é comum em C++, javascript e java: use a primeira letra maiúscula para os typedef

 

4 horas atrás, Lucas LC disse:

Não foi inicializado no método nessa parte eu já mudei, me equivoquei.

 

Se não disser onde e o que mudou não vou saber como arrumar seu programa em relação a id...

 

4 horas atrás, Lucas LC disse:
7 horas atrás, arfneto disse:

Um heap não é uma pilha. E pode ser visto como uma árvore binária  balanceada, exceto talvez por um nó.

Exatamente, ele não entra na definição de pilha e sim de uma árvore quase completa. 

 

Eu disse isso comentando a observação do tópico anterior...
 

7 horas atrás, KXSY disse:

É para fazer uma arvore binaria? ou seria um vetor organizado?

O elemento tem a prioridade separada ou ele mesmo é sua própria prioridade?

Fora que não seriam só essas questões, ainda há muito

mais

 

Se fosse eu faria assim, ignorando tudo que não faz sentido no enunciado

 

Eu sei o que você está escrevendo. A gente pode ver até pelo outro lado: Uma árvore binária balanceada é por definição um MaxHeap.

 

Poste seu programa como está agora. Ou altere direto aqui, usando um Pull Request. Eu não vou saber como corrigiu o problema com a variável id em removerElemento()

 

 

 

Li rapidamente seu programa a tarde. O que ainda não entendi: em geral Heap não usa ponteiros. Essa é afinal a grande vantagem dessa estrutura, que é muito muito rápida e baseada justamente em índices. Claro que os índices podem ser ponteiros, mas não entendo porque se faria isso. O que são os dois ponteiros que usa? heap e arranjo? Heap é ajustado sempre in-place...

 

Essencialmente um Max Heap --- ou um Min Heap --- se cuida sozinho. A cada mudança você chama max_heapify(). Só isso. 

 

 

 

Link para o comentário
Compartilhar em outros sites

19 horas atrás, arfneto disse:

Se não disser onde e o que mudou não vou saber como arrumar seu programa em relação a id...

Na verdade eu simplesmente tirei aquela parte e deixei a variável posição em 0, fiz a verificação da fila, se ela está vazia sim ou não, coloquei o endereço da primeira posição no ponteiro atual, decrementei o f->elementosNoHeap, coloquei o último elemento na primeira posição e chamei a reduzirPrioridadeAux, organizando meu heap. 

 

PONT removerElemento(PFILA f){
  PONT res = NULL;
  int id;
  PONT atual;
  int posicao = 0;
  //Verificar se a fila não está vazia. 
  if(f == NULL) return res; 
  if(f->elementosNoHeap == 0) return res; 
  
  //A primeira posição precisa ser excluida. 
  atual = f->heap[0];
  f->elementosNoHeap--;
  f->heap[0] = f->heap[f->elementosNoHeap];
  reduzirPrioridadeAux(f,0);
  
  
  //Colocar NULL na posição do arranjo.
  int excluir = atual->id; 
  f->arranjo[excluir] = NULL;

  
  res = atual; 
  return res;
}

 

19 horas atrás, arfneto disse:

Li rapidamente seu programa a tarde. O que ainda não entendi: em geral Heap não usa ponteiros. Essa é afinal a grande vantagem dessa estrutura, que é muito muito rápida e baseada justamente em índices. Claro que os índices podem ser ponteiros, mas não entendo porque se faria isso. O que são os dois ponteiros que usa? heap e arranjo? Heap é ajustado sempre in-place...

 

Essencialmente um Max Heap --- ou um Min Heap --- se cuida sozinho. A cada mudança você chama max_heapify(). Só isso. 

Nesse programa o  heap corresponde a um ponteiro para um arranjo de ponteiros para elementos do tipo ELEMENTO, este arranjo representará o heap máximo, seu tamanho será igual a maxElementos e o campo elementosNoHeap determinará quantos elementos válidos estão no heap em um dado momento e o arranjo corresponde a um ponteiro para um arranjo de ponteiros para elementos do tipo ELEMENTO, que irá guardar todos os elementos inseridos, a estrutura heap vai ter alguns métodos para fazer a manutenção dessa estrutura como esses dois que eu fiz

 

 

Esse aumentarPrioridadeAux2 será usando quando eu inserir um elemento na última posição ou aumentar a prioridade de algum elemento no arranjo e heap e preciso colocar ele no lugar certo do heap máximo, caso sua prioridade seja maior e o reduzirPrioridadeAux uso ele em reduzir prioridade para descer o elemento que tiver prioridade menor que seus filhos e caso o 1 elemento do heap seja excluido, ai eu excluo do heap e arranjo. 

 

 

exemplo: 

 

 

image.png.2f6fc6ff6e61f66551a9b2b5489f183d.png

 

//Função para trocar a posição dos elementos no heap.
void troca(PONT* a, PONT* b){
PONT t = *a;
*a = *b;
*b = t;

} 




//Se o atual tiver prioridade maior do que a de seu pai, os dois devem trocar de lugar).
void aumentarPrioridadeAux2(PFILA f, PONT atual){ 
 int i;
 for (i=0;i<f->elementosNoHeap;i++){
 atual = f->heap[i];
 if(atual->prioridade > f->heap[(i-1)/2]->prioridade){ 
 troca(&(atual), &(f->heap[(i-1)/2]));
  } 
       } 
            }







//Descer elemento no Heap
void reduzirPrioridadeAux(PFILA f, int posicao){
int maiorFilho = -1; 

for (posicao=0;posicao<f->elementosNoHeap;posicao++){

if(2*posicao+1 < f->elementosNoHeap){
maiorFilho = 2*posicao+1; 

if(2*posicao+2 < f->elementosNoHeap && (f->heap[2*posicao+1]->prioridade) < (f->heap[2*posicao+2]->prioridade))
maiorFilho = 2*posicao+2; 

if(maiorFilho>-1 && f->heap[posicao]->prioridade < f->heap[maiorFilho]->prioridade) { 
troca(&(f->heap[posicao]), &(f->heap[maiorFilho]));

}
    }  
        } 
            }

 

 

 

 

Não sei se deu para entender agora, o que estou com problemas é nessa função de troca, ele pode até trocar elementos de lugar, mas eles não trocam de posição.

Link para o comentário
Compartilhar em outros sites

1 hora atrás, Lucas LC disse:

Nesse programa o  heap corresponde a um ponteiro para um arranjo de ponteiros para elementos do tipo ELEMENTO, este arranjo representará o heap máximo, seu tamanho será igual a maxElementos e o campo elementosNoHeap determinará quantos elementos válidos estão no heap em um dado momento e o arranjo corresponde a um ponteiro para um arranjo de ponteiros para elementos do tipo ELEMENTO, que irá guardar todos os elementos inseridos, a estrutura heap vai ter alguns métodos para fazer a manutenção dessa estrutura como esses dois que eu fiz

 

Eu achei tudo isso muito confuso e complexo. Nesse programa um heap deve ser simplesmente um heap. Seu programa não deve introduzir um novo conceito.

 

Um heap é organizado in-place. Essa é uma característica essencial. E se a estrutura precisa mudar de tamanho pode usar o clássico, como em main(), já que dá certo em todo programa que já foi executado até hoje, como em 
 

        int main(int argc, char** argv);


Mas isso não tem a ver com o Heap. Apenas a representação. Assim, não consigo entender porque se pode precisar de dois grupos de ponteiros. E a noção de serem ELEMENTO** ou FILA** ** deveria sumir na lógica do programa, que iria simplesmente iterar por um vetor. De ponteiros ou inteiros ou de alicates de bico, tanto faz.

 

Apenas reajustando o tamanho do vetor --- mudando a posição da raiz --- e chamando Max_Heapify() o heap se auto-organiza. É uma estrutura meio mágica até. Num heap não existe prioridade. Talvez esteja misturando as coisas e daí venham os problemas.

 

Um heap não é uma fila de prioridade

 

Um heap pode ser usado para implementar uma fila de prioridade

 

E essa diferença é importante.

 

porque: A definição clássica:

 

uma fila de prioridade porque é uma estrutura de dados representando um conjunto S --- de Set --- onde cada elemento x --- da álgebra, sempre é :) x --- tem uma chave k --- de key --- associada e é a tal prioridade.

uma porque tem essas operações:
 

  • insert(S,x) - insere x em S, retorna 1 se alterou
  • max(S) - retorna o maior elemento de x
  • extract_max(S) - retorna e extrai o maior elemento de S
  • increase_key(S,x,k) - aumenta o valor da chave de x em S, a prioridade, assumida maior que o valor atual de k de x. Pode retornar 1 se alterou, por exemplo

Notou que nada fala sobre Heap? Referência: a bíblia de estruturas de dados

 

Heap: A definição clássica:

 

image.png.676bef3b4eabe8150d900e0d116f4bcf.png

 

Da mesma fonte.

 

Então um Heap é uma NCBT, uma árvore. E um array, vetor, arranjo, como queira.

 

Max_Heap e Min_Heap

 

Essas são propriedades de um Heap. Um Max_Heap é um Heap em que a chave de qualquer elemento é maior ou igual às chaves de seus filhos. Um Min_Heap é análogo.

 

Um Heap não envolve ponteiros!

 

Pois é: outra realidade importante. 

 

Operações em Heap

 

  • build_max_heap() - a partir de um vetor cria um max_heap
  • max_heapify() - corrige uma única não-conformidade  em um vetor que representa um heap a partir de um elemento e seus filhos
  • insert() - insere um elemento x em um Heap H
  • extract_max() - retorna e extrai o maior elemento, por definição a raiz

É só o que temos.

 

E onde deveria estar isso se juntando em seu código?

 

Seu programa deve tratar apenas com as funções da porque. Aquelas 4. A porque vai ser implementada como um Max_Heap() e então apenas as funções da porque falam com as funções do Heap. O conceito de encapsulamento afinal.

 

E os seus dados serão implementados na porque, seja uma ficha de consulta médica, seja a reserva de slot de decolagem no aeroporto, o despacho do pacote, a fila do banco com os idosos na frente, tanto faz. Seu programa fala com os seus dados, que falam com a porque, que fala com o Heap.

 

Não consigo ver isso no programa que escreveu e acho que por isso está tendo mais dificuldade do que o necessário.

 

Veja essa implementação de Max_Heapify() por exemplo, em 😄
 

int Max_Heapify(int S[], int raiz, int tamanho)
{
	int maior = raiz;
	int temp;
	int esq = raiz + raiz;// 2n
	int	dir = 1 + esq;// 2n + 1
	if (esq > tamanho) return 0;

	maior = (S[esq] > S[raiz]) ? esq : raiz;
	if (esq != (tamanho))
		if (S[dir] > S[maior]) maior = dir;

	if (maior != raiz)
	{	temp = S[raiz];
		S[raiz] = S[maior];
		S[maior] = temp;
		Max_Heapify(S, maior, tamanho);
	}	// end if
	return 0;
}	// end Max_Heapify()

 

Se você trocar as comparações por uma função e comparar com sua estrutura tem que funcionar. É só isso. Eu nem deixei comentários porque é apenas a transcrição da teoria. Em toda implementação que encontrar deve estar assim.


Sua estrutura estará organizada como Max_Heap num dado momento?
 

Por exemplo, essa função de 5 comandos retorna 1 se seu vetor é um Max_Heap(). É a definição. Mais uma vez, basta mudar a comparação e tem que funcionar para os seus dados.

 

int is_Max_Heap(int S[], int raiz, int tamanho)
{
	// retorna 1 se o conjunto S com tamanho 'tamanho'
	// e raiz em 'raiz' for um MaxHeap
	// nao usa o indice 0
	int esq = raiz + raiz;// 2n
	int	dir = 1 + esq;// 2n + 1
	if (esq > tamanho) return 1;
	if (dir > tamanho) return 1;
	if (S[esq] > S[raiz]) return 0; // violacao
	if (S[dir] > S[raiz]) return 0; // violacao
	return (is_Max_Heap(S, esq, tamanho) + is_Max_Heap(S, dir, tamanho)) == 2;
};	// is_Max_Heap()

 

Não é uma porque, não usa ponteiros e é muito rápido.

 

 

 

 

 

 

 

 

 

 

 

Link para o comentário
Compartilhar em outros sites

  • Solução

Ainda sobre esse programa:
 

Se você vai implementar uma P Q usando um Heap, e é uma escolha natural, e se tem essas funções 
 

int		build_max_heap(int[], int);
int		max_heapify(int[], int, int);

 

Então "pelo livro" faltam essas 
 

int		extract_max(int[], int);
int		heapsort(int[], int);
int		insert(int, int[], int);

 

No seu caso não é uma escolha natural, é apenas a expressão do enunciado.

 

Só que heap é uma estrutura self-healing: ela se ajusta sózinha. E extract_max() por exemplo pode ser só:
 

int		extract_max(int heap[], int tamanho)
{
	if (tamanho <= 0) return INT_MIN; // seria um erro
	int n = heap[1];
	heap[1] = heap[tamanho];
	tamanho -= 1;
	build_max_heap(heap, tamanho);
	return n;
};	// extract_max

 

Claro que int[ ] podia ser ELEMENTO* e extract_max() retornaria ELEMENTO ou ELEMENTO*, sem inventar. E continuaria com umas 5 linhas.

 

E insert()?

 

int		insert(int elem, int heap[], int tamanho)
{
	heap[++tamanho] = elem;
	build_max_heap(heap, tamanho);
	return 0;
};	// insert()

 

Pois é: 3 linhas. Tanto faz int[] ou ELEMENTO*

 

E o heapsort()?
 

int		hp_heapsort(int heap[], int tamanho)
{
	while (tamanho > 1)
		heap[tamanho--] = extract_max(heap, tamanho);
	return 0;
};	// heapsort()

 

Apenas duas linhas. E uma é o return. Podia retornar void porque heapsort() funciona in-place. Mais uma vez tanto faz se é int[] ou ELEMENTO* ou qualquer coisa.

 

E a fila de prioridade, onde entra?

 

A P Q tem essas funções: 
 

int	insert(Elem*, P Q*);
Elem	max(P Q*);
Elem	extract_max( P Q*);
int	increase_key(Elem*, P Q*, Key);

 

E ao usar um heap vai implementar a fila usando apenas as funções do heap. Nada mais. E elas se encaixam muito bem e por isso sempre se implementa P Q usando Heap

 

E não há ponteiros praticamente em lugar nenhum.

Se olhar para as funções que criou em seu programa vai ver como tudo fica simples ao considerar a existência da infra-estrutura do heap: a mágica do encapsulamento.

 

Exemplos em seu programa

 

Inserir
 

bool inserirElemento(PFILA f, int id, float prioridade);

 

Meio b3st@ esse lance de prioridade ser um float hein? Mas não faz diferença. Essa estrutura toda que recebeu é bem rudimentar...

 

Se a fila é implementada em um Heap, e Heap oferece 
 

int		insert(ELEMENTO Elem, ELEMENTO* Heap, int size);

 

Como está na lista, então inserir é trivial.


Outro:

 

int	removerElemento(ELEMENTO* elem, PFILA fila); 

 

Como a fila é um Max_Heap cada possível sub-conjunto da fila é um Max_Heap, por definição. Então você pode localizar o elemento na fila e usar extract_max() a partir dele e ele vai sumir da fila e reajustar tudo.

 

Outro:


Mudar prioridades. Não faz diferença aumentar ou diminuir. Num max_heap não está previsto diminuir, mas continua sendo um max_heap. Então pode localizar o elemento, copiar, excluir do heap com extract_max() e inserir com inserir() e passando a nova chave --- prioridade. É mais rápido e seguro. Não se manipula um heap diretamente como fez em seu programa. Uma alteração no heap() é realizada em logN operações recursivas. Muito rápido. 

 

No resto do programa não há qualquer menção a Heap ou Max_Heap. Apenas dentro das funções de P Q estão as chamadas às funções de manipulação de Heap. 

 

Não precisa nem sequer compilar as funções de Heap de novo. Basta o #include como faz com printf() por exemplo. E depois que a P Q funcionar pode usar em seus programas as funções de P Q sem se preocupar nem com P Q nem com Heap. O encapsulamento de novo.

 

E como costurar o programa, a P Q  o Heap?

 

Um algoritmo viável é usar uma estrutura tipo argc/argv de main() para alocar o Heap. deve dar certo já que sempre dá certo no sistema. E na construção se usam dois parâmetros: um tamanho inicial e um incremento. ex: 50 e 100. Então aloca um heap para 50 ponteiros para ELEMENTO na criação da fila e sempre que ele se esgotar se aloca MAIS 100 e corrige o tamanho: 50/150/250/350... Um Heap e não uma P Q. E mantem isso atualizado nos metadados da estrutura, claro.

 

O que é a P Q? um vetor. Num dado momento tem um certo número de elementos alocados e um certo número de elementos em uso.

 

Para a P Q  não é preciso usar ponteiros. E nem para o Heap. Apenas acontece que o Heap é alocado dinâmicamente e esses são os ponteiros. A fila usa índices para o Heap. O Heap usa índices para achar os elementos. Se o Heap for alocado estaticamente não há um ponteiro sequer.

 

Como destruir a P Q?

 

Nada especial: chama extract_max() até ela ficar vazia e apaga a estrutura, retornando NULL para invalidar o ponteiro...

 

Mais um exemplo:

 

Essa estrutura
 

typedef struct st_ex
{
	int	id;
	int	posicao;
	float	prioridade;

} ELEMENTO, * PONT;

typedef float		Key;
typedef ELEMENTO	Dado;

typedef struct
{
	Dado*   x;
	Key	k; // prioridade

}	Elemento;

typedef struct
{
	unsigned	incremento;
	unsigned	limite;
	unsigned	tamanho;
	Elemento**	E; // max_heap

}	P Q, S;

 

Provavelemente serviria para envolver seus dados e resolver seu programa de um modo bem simples, com funções de poucas linhas e fáceis de ler e alterar. E ficaria com as funções ;) tanto de heap quanto de p q para o futuro.

 

É preciso escrever P e Q separados porque o software b0b1nh0 desse forum troca p q por "porque" mesmo que sejam variáveis dentro de um programa. Genial!!!

image.png.818f55cc6a5337b485dad30b7421d259.png

Usei essa nomenclatura para poder ficar igual ao livro :). Só não usei os nomes em maiúscula porque em C não faria sentido...

Link para o comentário
Compartilhar em outros sites

  • 3 semanas depois...
Em 23/11/2020 às 17:38, arfneto disse:

Sua estrutura estará organizada como Max_Heap num dado momento?

Desculpa por sumir, estava com alguns problemas.

 

Então fiz sim maxHeap que chama uma função MaxHeapfy que faz essa manutenção, por exemplo: caso o elemento incluído no última posição ele é inserido e colocado na posição correta no heap usando a prioridade dele, a fila de prioridade fina no arranjo de ponteiros que guarda o endereço de todos os elementos inseridos, o heap seria uma forma de implementar os dois ao mesmo tempo esse trabalho. 

 

Consegui fazer já e está funcionando corretamente, colocarei no GitHub e mostrarei para você depois. 

Em 25/11/2020 às 00:10, arfneto disse:

E o heapsort()?

De acordo com o meu orientador não precisa de heapsort. 

Em 25/11/2020 às 00:10, arfneto disse:

Essa estrutura
 


typedef struct st_ex
{
	int	id;
	int	posicao;
	float	prioridade;

} ELEMENTO, * PONT;

typedef float		Key;
typedef ELEMENTO	Dado;

typedef struct
{
	Dado*   x;
	Key	k; // prioridade

}	Elemento;

typedef struct
{
	unsigned	incremento;
	unsigned	limite;
	unsigned	tamanho;
	Elemento**	E; // max_heap

}	P Q, S;

 

Provavelemente serviria para envolver seus dados e resolver seu programa de um modo bem simples, com funções de poucas linhas e fáceis de ler e alterar. E ficaria com as funções ;) tanto de heap quanto de p q para o futuro.

 

É preciso escrever P e Q separados porque o software b0b1nh0 desse forum troca p q por "porque" mesmo que sejam variáveis dentro de um programa. Genial!!!

image.png.818f55cc6a5337b485dad30b7421d259.png

Entendi arfneto, obrigado pelas dicas. 

Link para o comentário
Compartilhar em outros sites

Em 23/11/2020 às 17:38, arfneto disse:

Seu programa deve tratar apenas com as funções da porque. Aquelas 4. A porque vai ser implementada como um Max_Heap() e então apenas as funções da porque falam com as funções do Heap. O conceito de encapsulamento afinal

 

Em muitas partes desse post e talvez de outros o genial software do forum, esse InVision, troca P Q juntos por "porque". Bem *****. Mesmo que seja dentro de uma caixa de código. E no caso de você usar essas duas letras para identificar Priority Queue, que é bem comum, aparece "porque" no lugar e o texto fica sem sentido... Absurdo? Sim. Como é demorar 20s para trazer a lista dos últimos emoji utilizados. Mas a plataforma foi atualizada! 

 

Em 22/11/2020 às 19:53, arfneto disse:

Eu sei o que você está escrevendo. A gente pode ver até pelo outro lado: Uma árvore binária balanceada é por definição um MaxHeap

 

Desde que os nós atendam às propriedades do Min/Max Heap, claro

 

Em 16/12/2020 às 14:52, Lucas LC disse:

o heap seria uma forma de implementar os dois ao mesmo tempo esse trabalho

 

Entendo. Mas em geral o que se espera é implementar um ATRAVÉS do outro. A P Q implementada usando um MaxHeap, que é um Heap. É diferente.

 

Em 16/12/2020 às 14:52, Lucas LC disse:

De acordo com o meu orientador não precisa de heapsort

 

É claro que não. Não entendeu porque eu escrevi isso...
 

image.png.f76da1ec471a313c535f0532e379478d.png

 

Quando escrevi "pelo livro" eu só queria dizer isso. Para seguir as funções descritas na "bíblia" faltariam essas funções, e eu estava te mostrando como seria escrever a partir de um heap e das funções COMO DESCRITAS NO LIVRO de Corman e outros, a referência definitiva sobre essas coisas.

 

Até mostrei uma implementação:

 

int hp_heapsort(int heap[], int tamanho)
{ 
    while (tamanho > 1) heap[tamanho--] = extract_max(heap, tamanho);
    return 0;
}; // heapsort()

 

Mas é para ilustrar o que significa você implementar algo a partir de um Max/MinHeap, no sentido de que estou dizendo que formalmente você iria implementar a fila de prioridade usando um Heap. Usando somente as funções de Heap, sem misturar as coisas, como seria o caso se o Heap fosse fornecido pela linguagem. Separado. Espero que agora dê para entender melhor. Não sou seu orientador, no entanto ;) e se fosse você não usaria

 

Em 16/12/2020 às 14:52, Lucas LC disse:

uma forma de implementar os dois ao mesmo tempo esse trabalho

 

porque isso iria contra todo o princípio de objetos, encapsulamento e o princípio de não reinventar coisas.

 

:) 

Link para o comentário
Compartilhar em outros sites

Em 19/12/2020 às 13:29, arfneto disse:

Até mostrei uma implementação:

 


int hp_heapsort(int heap[], int tamanho)
{ 
    while (tamanho > 1) heap[tamanho--] = extract_max(heap, tamanho);
    return 0;
}; // heapsort()

 

Mas é para ilustrar o que significa você implementar algo a partir de um Max/MinHeap, no sentido de que estou dizendo que formalmente você iria implementar a fila de prioridade usando um Heap. Usando somente as funções de Heap, sem misturar as coisas, como seria o caso se o Heap fosse fornecido pela linguagem. Separado. Espero que agora dê para entender melhor. Não sou seu orientador, no entanto ;) e se fosse você não usaria

 

Em 16/12/2020 às 14:52, Lucas LC disse:

uma forma de implementar os dois ao mesmo tempo esse trabalho

 

porque isso iria contra todo o princípio de objetos, encapsulamento e o princípio de não reinventar coisas.

 

:) 

O arranjo correspondente ao heap não fica ordenado, por isso não precisamos do método heapSort em si: o arranjo corresponderá ao heap máximo: cada elemento terá prioridade maior ou igual à prioridade de seus filhos, mas não necessariamente será um arranjo ordenado.

Link para o comentário
Compartilhar em outros sites

1 hora atrás, Lucas LC disse:

O arranjo correspondente ao heap não fica ordenado, por isso não precisamos do método heapSort em si: o arranjo corresponderá ao heap máximo: cada elemento terá prioridade maior ou igual à prioridade de seus filhos, mas não necessariamente será um arranjo ordenado

 

Lucas, eu não consegui me explicar, mas vou tentar de novo: eu SEI que não tem a ver com seu problema. Eu só citei isso porque estava citando O LIVRO...
image.png.d3833395934891cb7793abc6ab085816.pngimage.png.dfc3fb3fb1f0028d77bf954fe74ed235.png


Pelo livro, o CLRS como é conhecido em todo o mundo...

É a referência definitiva há anos sobre estruturas de dados. Ouvi dizer que a versão em português tem muitos erros.

 

Eu me referia ao capítulo 6 desse livro quando escrevi "pelo livro" e não ao seu problema.

 

De volta ao seu programa
 

Isso era para ilustrar o que significa você implementar algo a partir de um Max/MinHeap, no sentido de que estou dizendo que formalmente você iria implementar a fila de prioridade usando um Heap. Como se usa HEap para HeapSort e uma infinidade de aplicações... Usando somente as funções de Heap, sem misturar as coisas, como seria o caso se o Heap fosse fornecido pela linguagem. Separado. Espero que agora dê para entender melhor. Não sou seu orientador, no entanto  e se fosse você não usaria assim ;) 

 

Abraço

 

 

 


 

Link para o comentário
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisa ser um usuário para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora

Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas comunidades sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×
×
  • Criar novo...