Heaps

Quins són els passos que s'ha de seguir en l'algoritme Heapsort? Juan Carlos Criado Beltrán
Primer pas: emmagatzemar tots els elements del vector a ordenar en un monticle (heap)
Segon pas: extraure l'element arrel del monticle (el mínim) en successives iteracions, obtenint el conjunt ordenat

Quins són els passos del mètode inserir de Monticle Binari? Raúl Talens Ferrer
Pas 1: S'insereix el nou element en la primera posició disponible del vector: elArray[talla + 1]
Pas 2: Es reflota sobre els seus antecessors fins que no viole la propietat d'ordre.

Cóm funciona el métode eliminar del Monticle Binari? Joan Ramón Esteve Chulià
Primer, convertim l'ultim element de l'arbre en l'arrel i decrementem la talla.
A continuació enfonsem la nova arrel fins que es torne a donar el ordre.

Donat el seguent array, [3,5,7,10,8,6,9], representa un MinHeap? Justifica la resposta. Genis Martinez Sanchis
No. La posició n = 6 (comencem a contar desde l'1 per a facilitar les operacions) del array conté un 6 y el seu pare, en la posicion 3 (n/2), conté un 7 sent el fill menor que el pare y per tant NO compleix l'ordre del Heap.

Quines són les propietats que caracteritzen un Monticle Binari? Elena Garrigós Candela
·Propietat estructural: és un arbre binari quasi-complet.
·Propietat d'ordre: en un MinHeap, els fills són més grans que el pare. En un MaxHeap, el pare és més gran que els fills.

Quina es la funció de heapify en un Monticle Binari? Álvaro Salvador González
Restableix la propietat d'ordre a partir d'un Arbre Binari Quasi-Complet per a obtenir un Monticle Binari.

Explica breument els pasos a seguir per a fer el mètode eliminar i quina semblança te amb el mètode inserir.Jean Fernandes
Si no està buit retorna i elimina la dada de menor prioritat. En un *minheap el node de menor prioritat és el primer, per la qual cosa en eliminar-ho trencaríem el monticle, haurem de moure l'últim al primer lloc, decrementar la talla i enfonsar-ho (heapify) fins que es complisca la propietat d'ordre.

Quin és el primer índex de l'array del heap en ser ocupat? Explica per què és aquest. Guillermo Montilla Tomás
El node arrel es situa en la posicio 1 (la 0 es deixa lliure, la qual cosa facilita el calcul dels fills d'un node)

Quin es el propòsit del heapify en un Monticle Binari?. Vicent Martinez Chulvi
El proposit o la funció es restableixer la propietat d'ordre a partir d'un arbre binari quasi-complet per a obtenir un monticle binari.

Que entenem per monticle binari maximal i per monticle binari minimal. Explica-ho i diferencia'ls. Sergi Vendrell García
El monticles maximals situen l'element més gran en l'arrel i la condició que han de complir és que els seus fills
siguen menors que el pare, en el minimal el mínim es situa en l'arrel i els seus fill han de ser majors al pare,
aquests es poden utilitzar per a representar cues de prioritat.

Quin és el valor de la posició d'un pare, donat la posició d'un element x (posX). Àngel Giner Vidal
Als heaps sabem que la posició dels fills d'un element és pos*2 (element de l'esquerra) i pos*2+1 (element de la dreta).
Per tant, podem afirmar que la posició d'un pare respecte a la del fill és la meitat: posX/2

Quin és el cost del HeapSort? Javier Contrí González
El cost del HeapSort és O(n ∗ log n)

En que es basa un heapify i quin és el seu cost? Àngel Chirlaque Zapata
Si es té un heap com a fill esq i un altre com a fill dret, es basa en enfonsar el node fins que trobe la seua posició natural.
El cost d'afonar un node de altura h és O(h).

Donat un minheap on es demana trobar totes les ocurrències de un determinat element, és necesari recorrer tots els elements del minheap? Justifica-ho.Víctor Cardona Lorenzo
Solució: No és necessari ja que es poden descartar aquelles branques que comparant-les siguen majors que l'element a trobar, evitant així recòrrer tots els elements.

Donat el heap [1,7,10,12,8,11,20,13,14,21,50,15], qui es fill del 20, en cas de tindre fills? Antonio Vte Molines Martin
El 20 esta en la posicio 7, el fill o fills estarien en la posicio 14 i 15, com son buides, 20 no te fills

Explica el mètode d'inserir. Arnau Ruiz Fuster
Es col·loca l'element en l'última posició + 1 i es reflota sobre els elements anteriors fins que la propietat d'ordre no es complisca.

Com implementaries un mètode que esborrara l'última fulla d'un heap minimal? Jesús Yáñez Signes
El procediment a seguir seria:
-Calcular la posició de la primera fulla del monticle com a (talla/2) + 1.
-Col·locar en aquesta posició l'últim element del array del monticle.
-Disminuir la talla.
-Reflotar l'element en la posició calculada fins que es complisca la propietat d'ordre del heap.

Què diferència un minheap de un maxheap? Joaquim Brines i García
En un minheap, la dada d'un node es sempre menor o igual que la dels seus fills, en canvi un maxheap es sempre major o igual.

És la seqüència {25, 20, 15, 21, 17, 14, 4, 3} un maxheap? Vicente Gavila Buigues
No, ja que la posicio n = 4 (començant a contar desde 1) hi ha un 21, i el seu pare en la posicio n = 2 conté un 20. Per tant la següent seqüència no pot ser un maxheap.

¿Qué consecuencias tiene la propiedad estructural del montículo binario. Es decir, que sea una árbol binario casi-completo? Tomás Ruiz Martín
-La posibilidad de representarlos de forma implícita en un array.
-El valor máximo de su altura, siendo esta LogN.
-Coste logarítmico en el caso peor, ya que tendría que recorrer una rama entera.

Donat un minheap [3,5,6,8,10,14,15,20,24,29], com podem saber si 10 te un node fill? Pablo de Polonia Llopis
Com tenim 10 elements, els nodes amb fills seràn els que estiguen entre les posicions 1 i 5 (per a una posició i, el fill esquerre està en 2*i, i el dret en 2*i+1). 2*5=10, com 10 està a la posició 5, serà l'ultim valor que tindrà fill (fill esquerre, en la posició 10, amb valor 29).

Quina és la forma més eficient d'inserir els elements d'un vector de N elements en un Heap? Pilar Piqueres Matoses
La forma més eficient és mitjançant el mètode arreglarMonticulo que té cost O(N) i manté la propietat d'ordre en els elements del Heap.

Explica el Métode "eliminar" del Monticle Binari. Robert Muradyan
El métode consta de dos passos: primer el nostre minim es troba en el node arrel, eixa dada es cambia pero l'ultim element del monticle i es disminueix la talla. El pas segon consta de que el nostre arrel s'enfonsa a través del fills fins que es cumplisca la condició d'ordre

És aquest array un minHeap? {5,6,7,15,35,8,12,8,20} Miguel García Bohigues
* no, si fem la representació de l'arbre, el node 15 té un fill amb valor 8.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License