I have a programming assignment as follows: You will need to convert the array into a heap using only O(n) swaps, as was described in the lectures. Note that you will need to use a min-heap instead of a max-heap in this problem. The first line of the output should contain single integer m — the total number of swaps. m must satisfy conditions 0 ≤ m ≤ 4n. The next m lines should contain the swap operations used to convert the array a into a heap. Each swap is described by a pair of integers i,j — the 0-based indices of the elements to be swapped
I have implemented a solution using sifting up technique by comparing with parent's value which gave solutions to small text cases, when number of integers in array is less than 10,verified by manual checking, but it could not pass the test case with 100000 integers as input. this is the code for that
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()
on the other hand i have implemented a heap sort using sifting down technique with similar comparing process, and this thing has passed every test case. following is the code for this method
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()
can someone explain what is wrong with sift/swap up method?
Trying to build a heap by "swapping up" from the bottom won't always work. The resulting array will not necessarily be a valid heap. For example, consider this array: [3,6,2,4,5,7,1]. Viewed as tree that is:
3
4 2
6 5 7 1
Your algorithm starts at the last item and swaps up towards the root. So you swap 1 with 2, and then you swap 1 with 3. That gives you:
1
4 3
6 5 7 2
You then continue with the rest of the items, none of which have to be moved.
The result is an invalid heap: that last item, 2, should be the parent of 3.
The key here is that the swapping up method assumes that when you've processed a[i], then the item that ends up in that position is in its final place. Contrast that to the swap down method that allows repeated adjustment of items that are lower in the heap.