Здание MIN-HEAP в Python

Question

Мне нужно построить полную реализацию MIN-HEAP в Python без использования встроенных функций кучи.

Так я получил определения родителя, левого и правого ребенка ребенка, которые принимают во внимание, что список номер питон элементов от 0:

from random import randint 
import math 

def parent(i): 
    x = int(l.index(l[i])) #########3 
    y = int(math.floor(x/2)) 
    return y-1 

def lchild(i): 
    x = int(l.index(l[i])) 
    y = int(math.floor(x*2)) 
    return y-1 

def rchild(i): 
    x = int(l.index(l[i])) 
    y = int(math.floor(x*2 + 1)) 
    return y-1 

то у меня есть часть кода, который генерирует (псевдо) случайный список для меня в список л:

l = [] 
dl = int(input) 

for i in range (0, dl): 
    x = int(randint(1,100)) 
    l.append(x)    

и до этого момента все работает хорошо. то у меня есть функция bkop для создания таблицы l в мини-кучу.

def bkop(l): 
     j = 0 
     for i in range(0, len(l)): 
       if int(l[i]) < int(parent(l[i])): #########2 
         l[i], l[parent(i)] = l[parent(i)], l[i] 
         j = j+1 
       if j != 0: 
         bkop(l) 

, то я хочу, чтобы запустить программу и увидеть результаты:

bkop(l) #########1 
print l 

программу падает с индексом списка ошибок из диапазона, указывающего на 3 линию, что я пометил с #########. Я начал писать об этом около месяца назад, и я уверен, что родитель, lchild и rchild работали в то время. Вы знаете, что случилось?

EDIT1: Итак, я исправил определения parent/lchild/rchild. Я проверил, они возвращают правильные значения. Вот код:

def parent(i): 
    x = i + 1 
    y = x//2 
    return y-1 

def lchild(i): 
    x = i + 1 
    y = x*2 
    return y-1 

def rchild(i): 
    x = i + 1 
    y = x*2 + 1 
    return y-1 

Функция, генерирующая случайный список, практически не повреждена. Тогда у меня есть эта функция bkop (что делает мини-кучу из списка l). Я использую печать до и после намеренно, если она работает ... и это не так. Он возвращает один и тот же список одновременно, без ошибок компиляции или чего-то еще. Любая идея, как это исправить?

print(l) 
def bkop(l): 
     j = 0 
     for i in range(0, len(l)): 
       if l[i] < parent(i): 
         l[i], l[parent(i)] = l[parent(i)], l[i] 
         j = j+1 
       if j != 0: 
         bkop(l) 
bkop(l) 
print l 

EDIT2: Хорошо, так что я фиксированной bkop как вы предложили:

print bkop(l) 
def bkop(l): 
     j = 0 
     for i in range(1, len(l)): 
       if l[i] < l[parent(i)]: 
         l[i], l[parent(i)] = l[parent(i)], l[i] 
         j = j+1 
       if j != 0: 
         bkop(l) 
bkop(l) 
print bkop(l) 

Но когда я запускаю его, я получаю эту первую сгенерированную случайным образом таблицу (как Я должен), а вместо таблицы мин-кучи, я получаю Отсутствует значение, как показано ниже:

[34, 9, 94, 69, 77, 33, 56] 
None 

Любой язь в виде? Может быть, я должен сделать это по-другому, не сравнивая l [i] с родителем, но l [i] с его левыми и правыми детьми?

Answer 1

Итак, у меня есть все, что работает с помощью Wombatz (Большое вам спасибо!). Вот рабочий код для будущих пользователей:

from random import randint 

def parent(i): 
    x = i + 1 
    y = x//2 
    return y-1 

def lchild(i): 
    x = i + 1 
    y = x*2 
    return y-1 

def rchild(i): 
    x = i + 1 
    y = x*2 + 1 
    return y-1 



l = [] 
dl = int(input()) 

for i in range (0, dl): 
    x = int(randint(1,100)) 
    l.append(x) 

print l 
def bkop(l): 
     j = 0 
     for i in range(1, len(l)): 
       if l[i] < l[parent(i)]: 
         l[i], l[parent(i)] = l[parent(i)], l[i] 
         j = j+1 
       if j != 0: 
         bkop(l) 
bkop(l) 
print l 

При запуске, я поставил 13 на входе в длину списка и я получил результат:

13 
[30, 62, 9, 100, 75, 73, 57, 82, 2, 76, 2, 50, 41] #before heapify 
[2, 2, 30, 62, 9, 41, 57, 100, 82, 76, 75, 73, 50] #after heapify 

Answer 2

На первый: есть проблема с parent, lchild и rchild функции:

• l[index] получает значение для данного показателя.

• l.index(...) получает индекс для заданного значения.

Вы пытаетесь получить индекс для значения по определенному индексу. Это как x + 1 - 1. Если ваши объекты уникальны, то этот вычисленный индекс всегда будет таким же, как и индекс, с которого вы начали. Когда есть дубликаты, ваши функции будут вычислять родительский, левый и правый дочерние элементы первого появления значения в этом индексе. Это, вероятно, не то, что вы хотите. Поэтому установите x на i или полностью удалите x.

Реальная проблема заключается в следующем:

Ваш parent, lchild и rchild функции обустроена работать на index но вы передаете значение l по индексу i функции: parent(l[i])

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

Кроме того:

parent, lchild и rchild возвращают неправильные значения. Протестируйте эту функцию без других вещей!

Я предполагаю, что результаты должны выглядеть следующим образом:

• parent(1) == parent(2) == 0
• lchild(0) == 1
• rchild(0) == 2

Ваше определение возвращает различные значения.

Некоторых мелкие вещи:

• Всех эти случайные int слепки бесполезны. Литье int в int ничего не делает. Единственной линией, которая действительно нужна, является: `` dl = int (input) `
• int(math.floor(x/2)). Используйте целочисленное деление x // 2 вместо
• int(math.floor(x*2)). Целочисленные времена 2 являются целыми числами. Нет необходимости в floor.

Редактировать Две вещи не так с вашей bkop функции.

• l[i] < parent(i) Вы сравниваете значение с индексом. Я думаю, вы хотите поставить в лагере значение на i на его родительское значение, а не на родительский индекс.
• для i == 0 вы сравниваете значение по индексу 0 со значением в parent(0) == -1.Это обертывает список и, вероятно, не то, что вы хотите. Поскольку индекс 0 не имеет родителя, вы не должны пытаться сравнивать его с его родителем.

Edit2

bkop не возвращает список, но изменяет его на месте. Просто print(l) в конце. Вы увидите, что исходный список был изменен.