Прайтон за приоритет на Python приоритет sift_up () - python, опашка, купчина, опашка приоритет

Все още съм съвсем нов за Python, но имам проблем с опашката с приоритетни купчини. Ето моите в него(), ул(), add () и моя метод sift_up ():

def __init__(self):
self.queue = []

def __str__(self):
return str(self.queue)

def add(self, item):
self.queue.append(item)
self.sift_up(len(self.queue) - 1)

def sift_up(self, item):
parent = (item - 1) // 2
if parent >= 0 and self.queue[parent] > self.queue[item]:
self.queue[parent], self.queue[item] = self.queue[item], self.queue[parent]
self.sift_up(parent)

Сега, когато добавям елементи към опашката, те вървят добре. Кажи, поставих това в терминал:

pq = PriorityQueue()
pq.add(1)
pq.add(2)
pq.add(45)
pq.add(4)
pq.add(41)
pq.add(5)

pq.__str__()

Това, което се връща, е "[1,2,5,4,41,45]". Така че изглежда sift_up () само донякъде, не се пренарежда напълно купчината.

EDIT: Изглежда, че се заклевам, когато добавя "1" към опашката. В този пример имах връщане след всяко добавяне:

>>> pq.add(5)
[5]
>>> pq.add(53)
[5, 53]
>>> pq.add(531)
[5, 53, 531]
>>> pq.add(5131)
[5, 53, 531, 5131]
>>> pq.add(1)
[1, 5, 531, 5131, 53]
>>>

Така че отнема всеки елемент е [1] и поставякъм задната част на опашката. Сигурен съм, че това е тривиално, но е новост за Python, не мога да разбера защо. Отново, всяка помощ е много ценена! Благодаря.

Отговори:

В примерните си данни, [5, 53, 531, 5131], изчислението, както го изразихте sift_up ще стане така:

# Append 1 to the end
--> [5, 53, 531, 5131, 1]

# The index for "1" is 4, so "item" is 4.
# (4-1) // 2 = 1 (and 1 >= 0), so "parent" is 1.
# The value at "parent" is 53. 53 > 1 is true.
# So swap the value 53 with the value at the end of the list.
--> [5, 1, 531, 5131, 53]

# Now repeat, "item" starts out at 1.
# The index at (1 - 1) // 2 = 0 (And 0 >=0) so "parent" is 0.
# The value at index 0 is 5. 5 > 1 is true.
# So swap the value 5 with the value at "item" (1) to get
--> [1, 5, 531, 5131, 53]

Така че този резултат следва логически от начина, по който сте кодирали sift_up.

Стандартната библиотека "s heapq.heapify функция също произвежда едно и също нещо: изглежда, че това е правилното поведение за приоритетна опашка:

In [18]: import heapq

In [19]: x = [5, 53, 531, 5131, 1]

In [20]: heapq.heapify(x)

In [21]: x
Out[21]: [1, 5, 531, 5131, 53]