Created
April 15, 2016 15:34
-
-
Save frootloops/b03e87b307c84ee2cd5dea00379d146d to your computer and use it in GitHub Desktop.
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
class BinHeap: | |
def __init__(self): | |
self.heapList = [0] | |
self.currentSize = 0 | |
self.swaps = [] | |
def percUp(self,i): | |
while i // 2 > 0: | |
if self.heapList[i] < self.heapList[i // 2]: | |
tmp = self.heapList[i // 2] | |
self.heapList[i // 2] = self.heapList[i] | |
self.heapList[i] = tmp | |
i = i // 2 | |
def insert(self,k): | |
self.heapList.append(k) | |
self.currentSize = self.currentSize + 1 | |
self.percUp(self.currentSize) | |
def percDown(self,i): | |
while (i * 2) <= self.currentSize: | |
mc = self.minChild(i) | |
if self.heapList[i] > self.heapList[mc]: | |
self.swaps.append(str(i - 1) + " " + str(mc - 1)) | |
tmp = self.heapList[i] | |
self.heapList[i] = self.heapList[mc] | |
self.heapList[mc] = tmp | |
i = mc | |
def minChild(self,i): | |
if i * 2 + 1 > self.currentSize: | |
return i * 2 | |
else: | |
if self.heapList[i*2] < self.heapList[i*2+1]: | |
return i * 2 | |
else: | |
return i * 2 + 1 | |
def delMin(self): | |
retval = self.heapList[1] | |
self.heapList[1] = self.heapList[self.currentSize] | |
self.currentSize = self.currentSize - 1 | |
self.heapList.pop() | |
self.percDown(1) | |
return retval | |
def buildHeap(self,alist): | |
i = len(alist) // 2 | |
self.currentSize = len(alist) | |
self.heapList = [0] + alist[:] | |
while (i > 0): | |
self.percDown(i) | |
i = i - 1 | |
bh = BinHeap() | |
bh.buildHeap([5, 4, 3, 2, 1]) | |
print(bh.swaps) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment