priority queues
TRANSCRIPT
Priority Queues
Ing. Andrea Quan
Priority Queues • Un priority queue es una estructura de datos que sirve
para manejar un conjunto de elementos, cada uno de los cuales esta asociado por un valor llamado key.
• La key asociada se puede reconocer como la prioridad del elemento.
Priority Queues • Un priority queue puede ser max-priority queue o
min-priority-queue. • Un max-priority queue soporta las siguientes
operaciones – INSERT à que inserta un elemento – MAXIMUM à que devuelve el elemento que tiene
la key (prioridad) mas grande – EXTRACT-MAX à saca y devuelve el elemento
con mayor key (prioridad) – INCREASE-KEY à incrementa el valor del key
(prioridad) de un elemento especifico
Priority Queues • Podemos utilizar un heap para implementar un priority
queue – Para implementar un max-priority queue se utiliza un
max-heap – Para implementar un min-priority queue se utiliza un
min-heap
Operaciones
• MAXIMUM HEAP-MAXIMUM(A) { return A[1] }
2
1
4 6 5
3
7
8 9 10 1
16
14 10
8 7 9
2 4
3
HEAP à 16 14 10 8 7 9 3 2 4 1
HEAP-MAXIMUM
Operaciones
• EXTRACT-MAX HEAP-EXTRACT-MAX(A) { if heap-size[A] < 1 { “Error, heap underflow” return null } else { max = A[1] A[1] = A[heap-size[A]] heap-size[A] = heap-size[A] – 1 MAX-HEAPIFY(A,1) return max } }
2
1
4 6 5
3
7
8 9 10 1
16
14 10
8 7 9
2 4
3
HEAP à 16 14 10 8 7 9 3 2 4 1
max = 16
heap-size = 10
2
1
4 6 5
3
7
8 9 10 16
1
14 10
8 7 9
2 4
3
HEAP à 1 14 10 8 7 9 3 2 4 16
max = 16
heap-size = 10
2
1
4 6 5
3
7
8 9 10 16
1
14 10
8 7 9
2 4
3
HEAP à 1 14 10 8 7 9 3 2 4 16
max = 16
heap-size = 9
2
1
4 6 5
3
7
8 9 10 16
14
8 10
4 7 9
2 1
3
HEAP à 14 8 10 4 7 9 3 2 1 16
max = 16
heap-size = 9
Operaciones
• INCREASE-KEY HEAP-INCREASE-KEY(A,i,key){ if key < A[i] { “Error nueva key menor que actual key” } else { A[i] = key while i > 1 and A[PARENT(i)] < A[i] { A[i] A[PARENT(i)] i = PARENT(i) } } }
2
1
4 6 5
3
7
8 9 10 1
16
14 10
8 7 9
2 4
3
HEAP à 16 14 10 8 7 9 3 2 4 1
i = 9
A[9] = 15
2
1
4 6 5
3
7
8 9 10 1
16
14 10
8 7 9
2 15
3
HEAP à 16 14 10 8 7 9 3 2 15 1
i = 9
Parent(i) = 4
2
1
4 6 5
3
7
8 9 10 1
16
14 10
15 7 9
2 8
3
HEAP à 16 14 10 15 7 9 3 2 8 1
i = 9
Parent(i) = 4
2
1
4 6 5
3
7
8 9 10 1
16
14 10
15 7 9
2 8
3
HEAP à 16 14 10 15 7 9 3 2 8 1
i = 4
Parent(i) = 2
2
1
4 6 5
3
7
8 9 10 1
16
15 10
14 7 9
2 8
3
HEAP à 16 15 10 14 7 9 3 2 8 1
i = 4
Parent(i) = 2
2
1
4 6 5
3
7
8 9 10 1
16
15 10
14 7 9
2 8
3
HEAP à 16 15 10 14 7 9 3 2 8 1
i = 2
Parent(i) = 1
2
1
4 6 5
3
7
8 9 10 1
16
15 10
14 7 9
2 8
3
HEAP à 16 15 10 14 7 9 3 2 8 1
Operaciones
• INSERT MAX-HEAP-INSERT(A,key) { heap-size[A] = heap-size[A] + 1 A[heap-size[A]] = -∞ HEAP-INCREASE-KEY(A,heap-size[A],key) }
2
1
4 6 5
3
7
8 9 10 1
16
15 10
14 7 9
2 8
3
- ∞ 11
HEAP à 16 15 10 14 7 9 3 2 8 1 - ∞
2
1
4 6 5
3
7
8 9 10 1
16
15 10
14 7 9
2 8
3
20 11
HEAP à 16 15 10 14 7 9 3 2 8 1 20
2
1
4 6 5
3
7
8 9 10 1
16
15 10
14 20 9
2 8
3
7 11
HEAP à 16 15 10 14 20 9 3 2 8 1 7
2
1
4 6 5
3
7
8 9 10 1
16
20 10
14 15 9
2 8
3
7 11
HEAP à 16 20 10 14 15 9 3 2 8 1 7
2
1
4 6 5
3
7
8 9 10 1
20
16 10
14 15 9
2 8
3
7 11
HEAP à 20 16 10 14 15 9 3 2 8 1 7
2
1
4 6 5
3
7
8 9 10 1
20
16 10
14 15 9
2 8
3
7 11
HEAP à 20 16 10 14 15 9 3 2 8 1 7