Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class BinHeap:
- def __init__(self, nondecreasing=True):
- self.heapList = [0]
- self.current_size = 0
- nondecreasing = True
- def build_heap(self, alist):
- i = len(alist) // 2
- self.current_size = len(alist)
- self.heapList = [0] + alist[:]
- print(len(self.heapList), i)
- while i > 0:
- print(self.heapList, i)
- self.perc_down(i)
- i = i - 1
- print(self.heapList, i)
- def perc_down(self, i):
- while (i * 2) <= self.current_size:
- mc = self.min_child(i)
- if self.heapList[i] > self.heapList[mc]:
- self.heapList[i], self.heapList[mc] = self.heapList[mc], self.heapList[i]
- i = mc
- def min_child(self, i):
- if i * 2 + 1 > self.current_size:
- return i * 2
- else:
- if self.heapList[i * 2] < self.heapList[i * 2 + 1]:
- return i * 2
- else:
- return i * 2 + 1
- def perc_up(self, i):
- while i // 2 > 0:
- if self.heapList[i] < self.heapList[i // 2]:
- self.heapList[i // 2], self.heapList[i] = self.heapList[i], self.heapList[i // 2]
- i = i // 2
- def insert(self, k):
- self.heapList.append(k)
- self.current_size = self.current_size + 1
- self.perc_up(self.current_size)
- def del_min(self):
- ret_val = self.heapList[1]
- self.heapList[1] = self.heapList[self.current_size]
- self.current_size = self.current_size - 1
- self.heapList.pop()
- self.perc_down(1)
- return ret_val
- def is_empty(self):
- return self.current_size == 0
- def __str__(self):
- returnstring = ""
- for i in range(len(self.heapList)):
- returnstring += str(self.heapList[i]) + " "
- return returnstring
- def __len__(self):
- return len(self.heapList)
- def findMaximumElement(self, heap, n):
- maximumElement = heap[0];
- j = 1
- for i in range(1, n):
- if self.heapList[i] > self.heapList[j]:
- j = i
- return j
- def findMinimumElement(self, heap, n):
- minimumElement = heap[0];
- j = 1
- for i in range(1, n):
- if self.heapList[j] > self.heapList[i]:
- j = i
- return j
- def sort(self, maxormin):
- if(maxormin == True):
- j = self.findMaximumElement(self.heapList, len(self.heapList))
- i = self.heapList[1]
- self.heapList[1], self.heapList[j] = self.heapList[j], self.heapList[1]
- for k in range(len(self.heapList)//2):
- for i in range(1,len(self.heapList)-1):
- j = i+1
- if(self.heapList[j] < self.heapList[i])-1:
- self.heapList[i], self.heapList[j] = self.heapList[j], self.heapList[i]
- elif(maxormin == False):
- j = self.findMinimumElement(self.heapList, len(self.heapList))
- i = self.heapList[1]
- self.heapList[1], self.heapList[j] = self.heapList[j], self.heapList[1]
- for k in range(len(self.heapList)//2):
- for i in range(1,len(self.heapList)-1):
- j = i+1
- if(self.heapList[j] > self.heapList[i])-1:
- self.heapList[i], self.heapList[j] = self.heapList[j], self.heapList[i]
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement