Guest User

Untitled

a guest
Dec 14th, 2018
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.22 KB | None | 0 0
  1. # python3
  2.  
  3. class HeapBuilder:
  4. def __init__(self):
  5. self._swaps = []
  6. self._data = []
  7.  
  8. def ReadData(self):
  9. n = int(input())
  10. self._data = [int(s) for s in input().split()]
  11. assert n == len(self._data)
  12.  
  13. def WriteResponse(self):
  14. #print(self._data)
  15. print(len(self._swaps))
  16. for swap in self._swaps:
  17. print(swap[0], swap[1])
  18.  
  19. def left(self,i):
  20. if i*2+1 >= len(self._data):
  21. return -1
  22.  
  23. return i*2+1
  24.  
  25. def write(self, i):
  26. if i * 2 + 2 >= len(self._data):
  27. return -1
  28.  
  29. return i * 2 + 2
  30.  
  31. def heapfy(self,i):
  32. minindex = i
  33. if self.left(i) != -1 and self._data[self.left(i)] < self._data[minindex]:
  34. minindex = self.left(i)
  35. if self.write(i)!=-1 and self._data[self.write(i)]<self._data[minindex]:
  36. minindex = self.write(i)
  37. if minindex !=i:
  38. self._swaps.append((i,minindex))
  39. self._data[i],self._data[minindex] = self._data[minindex],self._data[i]
  40.  
  41. self.heapfy(minindex)
  42.  
  43. def GenerateSwaps(self):
  44. for x in range(len(self._data)//2, -1 , -1):
  45. self.heapfy(x)
  46.  
  47.  
  48.  
  49. def Solve(self):
  50. self.ReadData()
  51. self.GenerateSwaps()
  52. self.WriteResponse()
  53.  
  54. if __name__ == '__main__':
  55. heap_builder = HeapBuilder()
  56. heap_builder.Solve()
Add Comment
Please, Sign In to add comment