# Binary Heap Object

I wrote a basic binary heap object in python 3, and was wondering how it can be improved to be cleaner and more pythonic.

import operator

class BinaryHeap:

def __init__(self, _comp = operator.gt):
self.heap = []
self.comp = _comp
# comparison operator used to order items in the heap
# comp(a,b) should return true if a should be stored
# above b in the heap
# comp(self.heap, self.heap[n]) will be true for
# any n (when the heap is valid)

# comp defaults to > which results in a maxheap

def __str__(self):
outStr = ""
n = 0
# put each layer of the stack on a different line
while pow(2,n)-1 < len(self.heap):
outStr += str( self.heap[pow(2,n)-1 :
min(pow(2,n+1)-1, len(self.heap))] ) + "\n"
n += 1
return outStr

def size(self):
return len(self.heap)

# returns true if item at i1 should be above that at i2
def compareAtIndices(self, i1,i2):
return self.comp(self.heap[i1], self.heap[i2])

# given a node's index, return the index of that node's first/second child
# (which is on the left/right when displayed graphically)
def leftChildIdx(self,i):
return 2*i + 1
def rightChildIdx(self,i):
return 2*i + 2

# given a node's index, return the index of that node's parent
def parentIdx(self,i):
return (i-1) // 2 # integer division to round down

# add an item to the stack, sorting to restore validity
def push(self, item):
self.heap.append(item)
self.upsort(len(self.heap)-1)

def pop(self):
if len(self.heap) == 0:
return
top = self.heap
if len(self.heap) > 1:
self.heap = self.heap.pop()
self.downsort(0)
else:
self.heap.pop()

# return the top element
def peek(self):
return self.heap

# move an item up, swaping it with its parent(s), to restore heap validity
def upsort(self, i):
if i <= 0:
return
pIdx = self.parentIdx(i)
if not self.compareAtIndices(pIdx, i):
self.swap(pIdx, i)
self.upsort(pIdx)

# move an item down, swaping it with its children, to restore heap validity
def downsort(self, i):
if i >= len(self.heap):
# no node at this index in the heap
return

lcIdx, rcIdx = self.leftChildIdx(i), self.rightChildIdx(i)
if lcIdx >= len(self.heap):
# no left child for node at this index
swapLeft = False
else:
swapLeft = self.compareAtIndices(lcIdx, i)

if rcIdx >= len(self.heap):
# no right child for node at this index
swapRight = False
else:
swapRight = self.compareAtIndices(rcIdx, i)

# if both children could be swapped with parent,
# compare them to decide which to swap
if swapLeft and swapRight:
# if self.compareAtIndices(lcIdx, rcIdx):
#     swapRight = False
# else:
#     swapLeft = False
swapLeft = self.compareAtIndices(lcIdx, rcIdx)
swapRight = not swapLeft

if swapLeft or swapRight:
self.swap(lcIdx if swapLeft else rcIdx, i)
self.downsort(lcIdx if swapLeft else rcIdx)

# swap elements at given indices
def swap(self,i1,i2):
self.heap[i1], self.heap[i2] = self.heap[i2], self.heap[i1]


The downsort method in particular feels messy (too many if statements), and I wasn't sure about naming of variables/methods.

• to make it more pythonic use snake_case, __len__ instead of size, key function instead of comparator and def sort(key, reversed=False) instead of two methods upsort and downsort. Sep 28, 2017 at 20:59

Yes, the variable naming should be improved:

• there is that lower_case_with_underscores style recommended for Python by PEP8
• I would probably, at least, use index variable name in place of i. And, lcIdx and rcIdx better off as left_index and right_index

There are some other PEP8 code style violations - like the spacing around the operators and the use of blank lines between the methods.

Also, you should move the comments before and after the class methods into proper documentation strings.

As far as reducing the number of if statement blocks in downsort, see if you can, at least, apply the short if/else versions - for example, this:

if lcIdx >= len(self.heap):
# no left child for node at this index
swapLeft = False
else:
swapLeft = self.compareAtIndices(lcIdx, i)


can be rewritten as:

swap_left = self.compareAtIndices(left_index, i) if left_index < len(self.heap) else False