C loop nos métodos de uma estrutura heap

Lucas LC · 21 de novembro de 2020

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;
}

arfneto · 21 de novembro de 2020

@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

Lucas LC · 22 de novembro de 2020

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

arfneto · 22 de novembro de 2020

@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.

Lucas LC · 22 de novembro de 2020

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.

arfneto · 22 de novembro de 2020

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.

Lucas LC · 23 de novembro de 2020

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:

//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.

arfneto · 23 de novembro de 2020

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:

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.

arfneto · 25 de novembro de 2020

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!!!

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...

Lucas LC · 16 de dezembro de 2020

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!!!

Entendi arfneto, obrigado pelas dicas.

arfneto · 19 de dezembro de 2020

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...

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.

Lucas LC · 21 de dezembro de 2020

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.

arfneto · 21 de dezembro de 2020

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...

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