У меня есть следующее программирование:
Вам нужно будет преобразовать массив в кучу, используя только O (n) подкачки, как было описано в лекциях. Обратите внимание, что вам нужно будет использовать min-heap вместо max-heap в этой проблеме. Первая строка вывода должна содержать одно целое число m - общее количество свопов. m должен удовлетворять условиям 0 ≤ m ≤ 4n. Следующие m строк должны содержать операции подкачки, используемые для преобразования массива a в кучу. Каждый своп описывается парой целых чисел i, j - индексами на основе 0 элементов, которые нужно поменять местами
Я реализовал решение, используя технику отсеивания, сравнивая со значением родителя, которое давало решения для небольших текстовых случаев, когда число целых чисел в массиве меньше 10, проверено ручной проверкой, но оно не может пройти тестовый пример с 100000 целых чисел в качестве входных данных.
это код для этого
class HeapBuilder:
def __init__(self):
self._swaps = [] #array of tuples or arrays
self._data = []
def ReadData(self):
n = int(input())
self._data = [int(s) for s in input().split()]
assert n == len(self._data)
def WriteResponse(self):
print(len(self._swaps))
for swap in self._swaps:
print(swap[0], swap[1])
def swapup(self,i):
if i !=0:
if self._data[int((i-1)/2)]> self._data[i]:
self._swaps.append(((int((i-1)/2)),i))
self._data[int((i-1)/2)], self._data[i] = self._data[i],self._data[int((i-1)/2)]
self.swapup(int((i-1)/2))
def GenerateSwaps(self):
for i in range(len(self._data)-1,0,-1):
self.swapup(i)
def Solve(self):
self.ReadData()
self.GenerateSwaps()
self.WriteResponse()
if __name__ == '__main__':
heap_builder = HeapBuilder()
heap_builder.Solve()
с другой стороны, я реализовал сортировку кучи, используя метод просеивания с аналогичным процессом сравнения, и эта вещь прошла каждый тестовый пример.
Ниже приведен код для этого метода
class HeapBuilder:
def __init__(self):
self._swaps = [] #array of tuples or arrays
self._data = []
def ReadData(self):
n = int(input())
self._data = [int(s) for s in input().split()]
assert n == len(self._data)
def WriteResponse(self):
print(len(self._swaps))
for swap in self._swaps:
print(swap[0], swap[1])
def swapdown(self,i):
n = len(self._data)
min_index = i
l = 2*i+1 if (2*i+1<n) else -1
r = 2*i+2 if (2*i+2<n) else -1
if l != -1 and self._data[l] < self._data[min_index]:
min_index = l
if r != - 1 and self._data[r] < self._data[min_index]:
min_index = r
if i != min_index:
self._swaps.append((i, min_index))
self._data[i], self._data[min_index] = \
self._data[min_index], self._data[i]
self.swapdown(min_index)
def GenerateSwaps(self):
for i in range(len(self._data)//2 ,-1,-1):
self.swapdown(i)
def Solve(self):
self.ReadData()
self.GenerateSwaps()
self.WriteResponse()
if __name__ == '__main__':
heap_builder = HeapBuilder()
heap_builder.Solve()
Может кто-нибудь объяснить, что не так с методом sift / swap up?