summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--sources/build_heap.py60
-rw-r--r--tests/build_heapTest.py25
2 files changed, 85 insertions, 0 deletions
diff --git a/sources/build_heap.py b/sources/build_heap.py
new file mode 100644
index 0000000..c880b0b
--- /dev/null
+++ b/sources/build_heap.py
@@ -0,0 +1,60 @@
+# python3
+
+
+def sift_down(i, data, swaps):
+ max_index = i
+ l = 2 * i + 1
+ if l < len(data) and data[l] < data[max_index]:
+ max_index = l
+ r = 2 * i + 2
+ if r < len(data) and data[r] < data[max_index]:
+ max_index = r
+ if i != max_index:
+ temp = data[i];
+ swaps.append((i, max_index))
+ data[i] = data[max_index]
+ data[max_index] = temp
+ sift_down(max_index, data, swaps)
+
+
+def get_swaps(data):
+ swaps = []
+ for i in range(int((len(data) - 1) / 2), -1, -1):
+ sift_down(i, data, swaps)
+ return swaps
+
+
+def build_heap(data):
+ """Build a heap from ``data`` inplace.
+
+ Returns a sequence of swaps performed by the algorithm.
+ """
+ # The following naive implementation just sorts the given sequence
+ # using selection sort algorithm and saves the resulting sequence
+ # of swaps. This turns the given array into a heap, but in the worst
+ # case gives a quadratic number of swaps.
+ #
+ swaps = []
+ for i in range(len(data)):
+ for j in range(i + 1, len(data)):
+ if data[i] > data[j]:
+ swaps.append((i, j))
+ data[i], data[j] = data[j], data[i]
+ return swaps
+
+
+def main():
+ n = int(input())
+ data = list(map(int, input().split()))
+ assert len(data) == n
+
+ # swaps = build_heap(data)
+ swaps = get_swaps(data)
+
+ print(len(swaps))
+ for i, j in swaps:
+ print(i, j)
+
+
+if __name__ == "__main__":
+ main()
diff --git a/tests/build_heapTest.py b/tests/build_heapTest.py
new file mode 100644
index 0000000..3b934bf
--- /dev/null
+++ b/tests/build_heapTest.py
@@ -0,0 +1,25 @@
+import unittest
+
+from sources.build_heap import get_swaps
+
+
+class MyTestCase(unittest.TestCase):
+ def test(self):
+ data = [5, 4, 3, 2, 1]
+ swaps = get_swaps(data)
+ self.assertEqual(len(swaps), 3)
+ self.assertEqual(1, swaps[0][0])
+ self.assertEqual(4, swaps[0][1])
+ self.assertEqual(0, swaps[1][0])
+ self.assertEqual(1, swaps[1][1])
+ self.assertEqual(1, swaps[2][0])
+ self.assertEqual(3, swaps[2][1])
+
+ def test1(self):
+ data = [1, 2, 3, 4, 5]
+ swaps = get_swaps(data)
+ self.assertEqual(len(swaps), 0)
+
+
+if __name__ == '__main__':
+ unittest.main()