Colas de prioridad en memoria secundaria
Jérémy Barbay 2 Sep 201002/09/10 a las 15:09 hrs.2010-09-02 15:09:02
2.3 Colas de prioridad en memoria secundaria.
[en.wikipedia.org/wiki/Priority_queue]
[en.wikipedia.org/ ... %28data_structure%29]
1) Colas de Prioridades tradicional:
- que se necesita?
* Operadores
- insert(key,item)
- findMind()
- extractMin()
* Operadores opcionales
- heapify
- increaseKey, decreaseKey
- find
- delete
- successor/predecessor
- merge
- ...
- diccionarios: demasiado espacio para que se pide
- menos operadores que diccionarios
- => mas flexibilidad en la representacion
- => mejor tiempo y/o espacio
- *binary heap*: una estructura a dentro de muchas otras:
- sequence-heaps
- binomial queues
- Fibonacci heaps
- leftist heaps
- min-max heaps
- pairing heaps
- skew heaps
- *van Emde Boas queues*
[www.itl.nist.gov/ ... TML/vanemdeboas.html]
- Definition: An efficient implementation of priority
queues where insert, delete, get minimum, get maximum,
etc. take O(log log N) time, where N is the total
possible number of keys. Depending on the circumstance,
the implementation is null (if the queue is empty), an
integer (if the queue has one integer), a bit vector of
size N (if N is small), or a special data structure: an
array of priority queues, called the bottom queues, and
one more priority queue of array indexes of the bottom
queues.
- rendimiento en memoria secundaria de "binary heap": muy malo?
2) Colas de Prioridades en Memoria Secundaria: diseno
* Reference:
+ [www.dcc.uchile.cl/ ... ritmos/tesisRapa.pdf]
- paginas 9 hasta 16
+ Otras referencias en [www.leekillough.com/heaps/]
- El equivalente de B-Arbol
- Muchas alternativas en practica
- Buffer trees
- M/B-ary heaps
- array heaps
- R-Heaps
- Array Heaps
- sequence heaps
- Mas en "An experimental study of priority queues in external memory"
[portal.acm.org/ ... cfm?id=351827.384259]
3) Colas de Prioridades en Memoria Secundaria: cota inferior?
- Cota inferior para dictionaries es una cota inferior por
colas de prioridades o no?
[en.wikipedia.org/wiki/Priority_queue]
[en.wikipedia.org/ ... %28data_structure%29]
1) Colas de Prioridades tradicional:
- que se necesita?
* Operadores
- insert(key,item)
- findMind()
- extractMin()
* Operadores opcionales
- heapify
- increaseKey, decreaseKey
- find
- delete
- successor/predecessor
- merge
- ...
- diccionarios: demasiado espacio para que se pide
- menos operadores que diccionarios
- => mas flexibilidad en la representacion
- => mejor tiempo y/o espacio
- *binary heap*: una estructura a dentro de muchas otras:
- sequence-heaps
- binomial queues
- Fibonacci heaps
- leftist heaps
- min-max heaps
- pairing heaps
- skew heaps
- *van Emde Boas queues*
[www.itl.nist.gov/ ... TML/vanemdeboas.html]
- Definition: An efficient implementation of priority
queues where insert, delete, get minimum, get maximum,
etc. take O(log log N) time, where N is the total
possible number of keys. Depending on the circumstance,
the implementation is null (if the queue is empty), an
integer (if the queue has one integer), a bit vector of
size N (if N is small), or a special data structure: an
array of priority queues, called the bottom queues, and
one more priority queue of array indexes of the bottom
queues.
- rendimiento en memoria secundaria de "binary heap": muy malo?
2) Colas de Prioridades en Memoria Secundaria: diseno
* Reference:
+ [www.dcc.uchile.cl/ ... ritmos/tesisRapa.pdf]
- paginas 9 hasta 16
+ Otras referencias en [www.leekillough.com/heaps/]
- El equivalente de B-Arbol
- Muchas alternativas en practica
- Buffer trees
- M/B-ary heaps
- array heaps
- R-Heaps
- Array Heaps
- sequence heaps
- Mas en "An experimental study of priority queues in external memory"
[portal.acm.org/ ... cfm?id=351827.384259]
3) Colas de Prioridades en Memoria Secundaria: cota inferior?
- Cota inferior para dictionaries es una cota inferior por
colas de prioridades o no?
| Última Modificación | 2 Sep 201002/09/10 a las 15:09 hrs.2010-09-02 15:09:02 |
|---|---|
| Vistas Únicas | 0 |
| Compartir |
