простая минимальная куча в python Использование списка с элементами Tuple (неизменяемые) - PullRequest
Новая
       30

простая минимальная куча в python Использование списка с элементами Tuple (неизменяемые)

0 голосов
/ 08 декабря 2018

В настоящее время я делаю курс по edx, и одной из задач является реализация простой мини-кучи.

Куча должна быть реализована с использованием списка кортежей, которые являются неизменяемыми, поэтому их нельзя изменить на месте.

  • Первый элемент кортежа - это ключ
  • Второй элемент - это проверяемая переменная на предмет минимального значения
  • Элемент 3 является посторонним

Мое решение приведено ниже, но, поскольку я новичок в python, я хотел бы знать, как его реализует более опытный программист, но с существующими ограничениями списка кортежей - никакие другие структуры данных не могут быть использованы.

def heap_add_or_replace(heap, triplet):
match=0
for tup in heap[:]:
    if tup[0]==triplet[0]:
        match+=1
        if tup[1] > triplet[1]:
            heap.remove(tup)
            heap.append(triplet)
            break
if  match==0:
    heap.append(triplet)

heap.sort(key=lambda x:x[1])

Тесты курса включены ниже: 

#
# AUTOGRADER TEST - DO NOT REMOVE
#

triplet_heap=list()

heap_add_or_replace(triplet_heap,((2,3),0.9,(1,0)))
print("the new heap is: "+str(triplet_heap))

heap_add_or_replace(triplet_heap,((7,2),0.3,(2,2)))
print("the new heap is: "+str(triplet_heap))

heap_add_or_replace(triplet_heap,((3,2),1,(2,2)))
print("the new heap is: "+str(triplet_heap))

print("the new heap is: "+str(triplet_heap))

heap_add_or_replace(triplet_heap,((7,2),0.2,(2,3)))
print("the new heap is: "+str(triplet_heap))

heap_add_or_replace(triplet_heap,((1,2),0.3,(2,3)))
print("the new heap is: "+str(triplet_heap))

heap_add_or_replace(triplet_heap,((1,2),0.1,(2,3)))
print("the new heap is: "+str(triplet_heap))

heap_add_or_replace(triplet_heap,((1,2),0.05,(2,0)))
print("the new heap is: "+str(triplet_heap))

heap_add_or_replace(triplet_heap,((4,6),2,(2,3)))
print("the new heap is: "+str(triplet_heap))

heap_add_or_replace(triplet_heap,((1,2),0.01,(2,0)))
print("the new heap is: "+str(triplet_heap))

heap_add_or_replace(triplet_heap,((4,6),9,(2,3)))
print("the new heap is: "+str(triplet_heap))

и ожидаемые результаты: 

the new heap is: [((2, 3), 0.9, (1, 0))]
the new heap is: [((7, 2), 0.3, (2, 2)), ((2, 3), 0.9, (1, 0))]
the new heap is: [((7, 2), 0.3, (2, 2)), ((2, 3), 0.9, (1, 0)), ((3, 2), 1, (2, 2))]
the new heap is: [((7, 2), 0.3, (2, 2)), ((2, 3), 0.9, (1, 0)), ((3, 2), 1, (2, 2))]
the new heap is: [((7, 2), 0.2, (2, 3)), ((2, 3), 0.9, (1, 0)), ((3, 2), 1, (2, 2))]
the new heap is: [((7, 2), 0.2, (2, 3)), ((1, 2), 0.3, (2, 3)), ((2, 3), 0.9, (1, 0)), ((3, 2), 1, (2, 2))]
the new heap is: [((1, 2), 0.1, (2, 3)), ((7, 2), 0.2, (2, 3)), ((2, 3), 0.9, (1, 0)), ((3, 2), 1, (2, 2))]
the new heap is: [((1, 2), 0.05, (2, 0)), ((7, 2), 0.2, (2, 3)), ((2, 3), 0.9, (1, 0)), ((3, 2), 1, (2, 2))]
the new heap is: [((1, 2), 0.05, (2, 0)), ((7, 2), 0.2, (2, 3)), ((2, 3), 0.9, (1, 0)), ((3, 2), 1, (2, 2)), ((4, 6), 2, (2, 3))]
the new heap is: [((1, 2), 0.01, (2, 0)), ((7, 2), 0.2, (2, 3)), ((2, 3), 0.9, (1, 0)), ((3, 2), 1, (2, 2)), ((4, 6), 2, (2, 3))]
the new heap is: [((1, 2), 0.01, (2, 0)), ((7, 2), 0.2, (2, 3)), ((2, 3), 0.9, (1, 0)), ((3, 2), 1, (2, 2)), ((4, 6), 2, (2, 3))]
...