#!/usr/bin/env python3
class PriorityQueue:
def pop(self):
""" returns a most prioritzed element
Raises:
NotImplementedError: _description_
"""
raise NotImplementedError
def push(self, el) -> None:
raise NotImplementedError
def isEmpty(self) -> bool:
raise NotImplementedError
def update(self, el) -> None:
raise NotImplementedError
class HeapQueue(PriorityQueue):
def __init__(self, key=lambda x: x):
self.repr = []
self.key = key
def parent(self, i):
return (i-1) // 2
def leftChild(self, i):
return 2*i+1
def rightChild(self, i):
return 2*(i+1)
def swap(self, i, j):
self.repr[i], self.repr[j] = self.repr[j], self.repr[i]
def push(self, el):
self.repr.append(el)
indice = len(self.repr) - 1
parent = self.parent(indice)
while indice > 0 and self.key(self.repr[parent]) >= self.key(self.repr[indice]):
self.swap(parent, indice)
indice = parent
parent = self.parent(indice)
def pop(self):
m = self.repr[0]
self.repr[0] = self.repr.pop()
indice = 0
leftChild = self.leftChild(indice)
rightChild = self.rightChild(indice)
while leftChild < len(self.repr):
if self.key(self.repr[leftChild]) < self.key(self.repr[rightChild]) and self.key(self.repr[leftChild]) < self.key(self.repr[indice]):
self.swap(leftChild, indice)
indice = leftChild
leftChild = self.leftChild(indice)
rightChild = self.rightChild(indice)
if self.key(self.repr[rightChild]) <= self.key(self.repr[leftChild]) and self.key(self.repr[rightChild]) < self.key(self.repr[indice]):
self.swap(rightChild, indice)
indice = rightChild
leftChild = self.leftChild(indice)
rightChild = self.rightChild(indice)
else:
leftChild = len(self.repr)
if __name__ == "__main__":
hq = HeapQueue()
hq.push(4)
hq.push(5)
hq.push(1)
print(hq.repr)
class PriorityQueue:
"""Implementation of a max priority queue garanting insertion in O(1), peeking in O(1) and pulling element of **highest** priority in O(n)"""
def __init__(self):
self.elements = []
def push(self, elem):
"""Push a tuple (priority, value) to the queue"""
priority, value = elem
if priority > self.elements[0][0]:
self.elements = [(priority, value)] + self.elements
else:
self.elements.append((priority, value))
def peek(self):
"""Look at the element of top priority"""
return self.elements[0]
def pop(self):
"""Retrieves and removes the element of top priority"""
highest = self.elements[0]
if len(self.elements) == 1:
self.elements.remove(highest)
return highest
new_highest_index = 1
for i in range(2, len(self.elements)):
if self.elements[i][0] > self.elements[new_highest_index][0]:
new_highest_index = i
temp = self.elements[1]
self.elements[1] = self.elements[new_highest_index]
self.elements[new_highest_index] = temp
self.elements.remove(highest)
return highest
class HeapQueue(PriorityQueue):
"""Min Heap implementation
Switch to Max Heap with `reverse = True`
"""
def __init__(self, *, key=lambda x: x, reverse: bool = False):
super().__init__()
self.lt = lambda x, y: key(x) < key(y) if reverse else key(x) > key(y)
def parent(i):
return int((i - 1) / 2)
def left_child(i):
return (i * 2) + 1
def right_child(i):
return (i * 2) + 2
def swap(self, i, j):
temp = self.elements[i]
self.elements[i] = self.elements[j]
self.elements[j] = temp
def sift_up(self, i):
while i != 0 and not self.lt(
self.elements[i], self.elements[HeapQueue.parent(i)]
):
self.swap(i, HeapQueue.parent(i))
i = HeapQueue.parent(i)
def push(self, elem):
i = len(self.elements)
self.elements.append(elem)
self.sift_up(i)
def sift_down(self, i):
n = len(self.elements)
# swap elements until either there is at most one child remaining or both children are smaller
while (
HeapQueue.left_child(i) < n - 1
and self.lt(self.elements[i], self.elements[HeapQueue.left_child(i)])
) and (
HeapQueue.right_child(i) < n - 1
and self.lt(self.elements[i], self.elements[HeapQueue.right_child(i)])
):
if self.lt(
self.elements[HeapQueue.right_child(i)],
self.elements[HeapQueue.left_child(i)],
):
self.swap(i, HeapQueue.left_child(i))
i = HeapQueue.left_child(i)
else:
self.swap(i, HeapQueue.right_child(i))
i = HeapQueue.right_child(i)
while HeapQueue.left_child(i) < n - 1 and self.lt(
self.elements[i], self.elements[HeapQueue.left_child(i)]
):
self.swap(i, HeapQueue.left_child(i))
i = HeapQueue.left_child(i)
while HeapQueue.right_child(i) < n - 1 and self.lt(
self.elements[i], self.elements[HeapQueue.right_child(i)]
):
self.swap(i, HeapQueue.right_child(i))
i = HeapQueue.right_child(i)
def pop(self):
n = len(self.elements)
self.swap(0, n - 1)
self.sift_down(0)
top = self.elements[n - 1]
self.elements.remove(top)
return top
def update(self, old_val, new_val):
i = self.elements.index(old_val)
self.elements[i] = new_val
if self.lt(old_val, new_val):
self.sift_up(i)
else:
self.sift_down(i)
def __repr__(self):
return repr(self.elements)
def __len__(self):
return len(self.elements)
def heap_sort(l, *, key=lambda x: x, reverse=False):
"""Sorts l with a heap sort according to the key `key`"""
hq = HeapQueue(key=key, reverse=reverse)
for e in l:
hq.push(e)
return [hq.pop() for _ in range(len(hq))]
if __name__ == "__main__":
hq = HeapQueue()
hq.push(10)
hq.push(4)
hq.push(7)
hq.push(2)
hq.push(1)
hq.push(9)
hq.push(8)
hq.push(12)
hq.push(3)
print(hq)
hq.update(12, 6)
print(hq)
while hq:
print(hq.pop())
l = [10, 4, 7, 2, 1, 9, 8, 12, 3]
print(l, heap_sort(l, reverse=True))
#!/usr/bin/env python3
def parent(i) -> int: return (i - 1) // 2
def leftChild(i) -> int: return 2 * i + 1
def rightChild(i) -> int: return 2 * i + 2
class HeapQueue:
def __init__(self):
self.heap = []
self.size = 0
def swap(self, i, j):
self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
def siftUp(self, i):
while i > 0 and self.heap[parent(i)] > self.heap[i]:
self.swap(i, parent(i))
i = parent(i)
def push(self, value):
self.heap.append(value)
self.size += 1
self.siftUp(self.size - 1)
def siftDown(self, i):
minIndex = i
l = leftChild(i)
if l < self.size and self.heap[l] < self.heap[minIndex]:
minIndex = l
r = rightChild(i)
if r < self.size and self.heap[r] < self.heap[minIndex]:
minIndex = r
if i != minIndex:
self.swap(i, minIndex)
self.siftDown(minIndex)
def pop(self):
result = self.heap[0]
self.heap[0] = self.heap[self.size - 1]
self.size -= 1
self.siftDown(0)
return result
def update(self, i, value):
old_value = self.heap[i]
self.heap[i] = value
if value > old_value:
self.siftDown(i)
else:
self.siftUp(i)
#!/usr/bin/env python3
import HeapQueue
def heapSort(l, **kwargs):
h = HeapQueue.HeapQueue()
if 'key' in kwargs:
l = [*map(lambda x: (kwargs['key'](x), x), l)]
for i in l:
h.push(i)
nl = []
for i in range(h.size):
if 'key' in kwargs:
nl.append(h.pop()[1])
else:
nl.append(h.pop())
if 'reverse' in kwargs and kwargs['reverse']:
nl.reverse()
return nl
#!/usr/bin/env python3
import json
from heapQueue import HeapQueue
class TEI:
def __init__(self, filename):
with open(filename) as f:
self.data = json.load(f)
def path(self, start, end):
# applique l'algorithme de Dijkstra pour trouver le chemin le plus court
# entre start et end
# retourne une liste de noeuds
h = HeapQueue()
h.push((0, [start]))
visited = {}
while h.size > 0:
cost, nodes = h.pop()
node, *_ = nodes
if node in visited:
continue
visited[node] = 1
if node == end:
nodes.reverse()
return nodes
for neighbor in self.data[node]:
if neighbor not in visited:
h.push((cost + 1, [neighbor, *nodes]))
class PriorityQueue():
# Classe abstraite de file de priorité
def __init__(self, priority):
self.priority = priority
def push(self, x):
pass
def pop(self):
pass
def isempty(self):
pass
def update(self, x):
pass
class HeapQueue(PriorityQueue):
# Implémentation d'une file de priorité avec un tas
def __init__(self):
# Création d'un tas vide
self.heap = []
self.size = 0
def parent(self, i):
# Revoie l'index du parent du noeud d'index i
return i//2
def leftChild(self, i):
# Revoie l'index de l'enfant gauche du noeud d'index i
return 2*i + 1
def rightChild(self, i):
# Revoie l'index de l'enfant droite du noeud d'index i
return 2*i + 2
def swap(self, i, j):
# Échange les valeurs des noeuds d'index i et j
self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
def remonte(self, i, key = lambda x : x):
# Fait remonter dans le tas la valeur du noeud d'index i
# jusqu'à ce qu'elle soit supérieure à ses parents
while key(self.heap[i]) < key(self.heap[self.parent(i)]): #parent(0) = 0 ce qui est bien pratique
self.swap(i, self.parent(i))
i = self.parent(i)
def descend(self, i, key = lambda x : x):
# Fait descendre dans le tas la valeur du noeud d'index i
# jusqu'à ce qu'elle soit supérieure à ses parents
while (self.rightChild(i) < self.size
and key(self.heap[i]) > min(key(self.heap[self.leftChild(i)]), key(self.heap[self.rightChild(i)]))):
if key(self.heap[self.rightChild(i)]) < key(self.heap[self.leftChild(i)]):
self.swap(i, self.rightChild(i))
i = self.rightChild(i)
else:
self.swap(i, self.leftChild(i))
i = self.leftChild(i)
if (self.leftChild(i) < self.size
and key(self.heap[i]) > key(self.heap[self.leftChild(i)])):
self.swap(i, self.leftChild(i))
def push(self, a, key = lambda x : x):
# Ajoute un élément au tas en préservant la structure
if self.size == len(self.heap):
self.heap.append(a)
else:
self.heap[self.size] = a
i = self.size
self.size += 1
self.remonte(i, key)
def pop(self, i, key = lambda x : x):
# Retire et renvoie un élément du tas en préservant la structure
self.swap(i, self.size - 1)
self.size -= 1
self.descend(i, key)
return self.heap[self.size]
def update(i, a, key = lambda x : x):
# Met à jour la valeur du noeud d'index i en préservant la structure
if a < self.heap[i]:
self.heap[i] = a
self.remonte(i, key)
elif a > self.heap[i]:
self.heap[i] = a
self.descend(i, key)
def heap_sort(l, key = lambda x : x, reverse = False):
# Tri par tas
heap = HeapQueue()
for x in l:
heap.push(x, key)
l_tri = [heap.pop(0, key) for x in l]
if reverse:
l_tri.reverse()
return l_tri