From 602995c859265493dd94996d1626e6de44d512e6 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Sun, 17 Feb 2019 09:35:46 -0600
Subject: Build heap done!

Not too bad, since the Java version has been worked out.
---
 sources/build_heap.py   | 60 +++++++++++++++++++++++++++++++++++++++++++++++++
 tests/build_heapTest.py | 25 +++++++++++++++++++++
 2 files changed, 85 insertions(+)
 create mode 100644 sources/build_heap.py
 create mode 100644 tests/build_heapTest.py

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()
-- 
cgit v1.2.3