Created
April 19, 2018 09:30
-
-
Save lttzzlll/09014d8eea6bde99e651895ec9e86fb8 to your computer and use it in GitHub Desktop.
heap sort using heapq
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import random | |
def heap_sort(ints): | |
heapify(ints) | |
res = [] | |
while ints: | |
res.append(heappop(ints)) | |
return res | |
def heappop(heap): | |
"""Pop the smallest item off the heap, maintaining the heap invariant.""" | |
lastelt = heap.pop() # raises appropriate IndexError if heap is empty | |
if heap: | |
returnitem = heap[0] | |
heap[0] = lastelt | |
_siftup(heap, 0) | |
return returnitem | |
return lastelt | |
def heapify(x): | |
"""Transform list into a heap, in-place, in O(len(x)) time.""" | |
n = len(x) | |
# Transform bottom-up. The largest index there's any point to looking at | |
# is the largest with a child index in-range, so must have 2*i + 1 < n, | |
# or i < (n-1)/2. If n is even = 2*j, this is (2*j-1)/2 = j-1/2 so | |
# j-1 is the largest, which is n//2 - 1. If n is odd = 2*j+1, this is | |
# (2*j+1-1)/2 = j so j-1 is the largest, and that's again n//2-1. | |
for i in reversed(range(n//2)): | |
_siftup(x, i) | |
def _siftup(heap, pos): | |
endpos = len(heap) | |
startpos = pos | |
newitem = heap[pos] | |
# Bubble up the smaller child until hitting a leaf. | |
childpos = 2*pos + 1 # leftmost child position | |
while childpos < endpos: | |
# Set childpos to index of smaller child. | |
rightpos = childpos + 1 | |
if rightpos < endpos and not heap[childpos] < heap[rightpos]: | |
childpos = rightpos | |
# Move the smaller child up. | |
heap[pos] = heap[childpos] | |
pos = childpos | |
childpos = 2*pos + 1 | |
# The leaf at pos is empty now. Put newitem there, and bubble it up | |
# to its final resting place (by sifting its parents down). | |
heap[pos] = newitem | |
_siftdown(heap, startpos, pos) | |
def _siftdown(heap, startpos, pos): | |
newitem = heap[pos] | |
# Follow the path to the root, moving parents down until finding a place | |
# newitem fits. | |
while pos > startpos: | |
parentpos = (pos - 1) >> 1 | |
parent = heap[parentpos] | |
if newitem < parent: | |
heap[pos] = parent | |
pos = parentpos | |
continue | |
break | |
heap[pos] = newitem | |
def test(): | |
ints = random.sample(range(1, 100), 10) | |
print(ints) | |
ints = heap_sort(ints) | |
print(ints) | |
for i in range(len(ints) - 1): | |
if ints[i] > ints[i + 1]: | |
print('Error') | |
break | |
def main(): | |
for _ in range(1000): | |
test() | |
if __name__ == '__main__': | |
main() | |
# refer [heapq](https://docs.python.org/3.5/library/heapq.html) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment