summaryrefslogtreecommitdiff
path: root/sources
diff options
context:
space:
mode:
authorHaidong Ji2019-02-17 09:35:46 -0600
committerHaidong Ji2019-02-17 09:35:46 -0600
commit602995c859265493dd94996d1626e6de44d512e6 (patch)
tree0784aeb347cb3a6e25eae77007c2fbe1f420f4f8 /sources
parente314d433e66a6177c8a17e3fca5acc59005e1b06 (diff)
Build heap done!
Not too bad, since the Java version has been worked out.
Diffstat (limited to 'sources')
-rw-r--r--sources/build_heap.py60
1 files changed, 60 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()