I'm having to convert some C++ code to Python for a deployment and am currently struggling in implementing the C++ STL Heap data structure.
I currently have the following class implemented in Python:
class Heap:
def __init__(self):
self.heap = []
def heap_swap(self, a, b):
t = self.heap[a]
self.heap[a] = self.heap[b]
self.heap[b] = t
def _heapify(self, heap_size, x, predicate):
left = 2 * (x + 1) - 1
right = 2 * (x + 1)
largest = x
if left < heap_size and predicate(self.heap[left], self.heap[x]):
largest = left
if right < heap_size and predicate(self.heap[right], self.heap[largest]):
largest = right
if largest != x:
self.heap_swap(x, largest)
self._heapify(heap_size, largest, predicate)
def make_heap(self, h, comp=max_predicate):
self.heap = h
heap_size = len(self.heap)
for i in reversed(range(0, heap_size //2)):
self._heapify(heap_size, i, comp)
def pop_heap(self, predicate):
pop_value = self.heap[0]
self.heap_swap(0, len(self.heap)-1)
self._heapify(len(self.heap) -1, 0, predicate)
return pop_value
def push_heap(self, value, predicate=max_predicate):
self._heap.append(value)
current = len(self.heap) - 1
while current > 0:
parent = (current - 1) // 2
if predicate(self.heap[current], self.heap[parent]):
self.heap_swap(parent, current)
current = parent
else:
break
In order to test the functionality, I've written the following C++ file:
// range heap example
#include <iostream> // std::cout
#include <algorithm> // std::make_heap, std::pop_heap, std::push_heap, std::sort_heap
#include <vector> // std::vector
bool comp (int i,int j) { return (i >= j); }
int main () {
int myints[] = {694 ,1054, 2121 ,4, 878};
std::vector<int> v(myints,myints+5);
std::make_heap (v.begin(),v.end());
return 0;
}
Now if I run:
std::pop_heap(v.begin(), v.end());
I get:
1054 878 694 4 2121
If I try it in Python using:
if __name__ == "__main__":
h = Heap()
heap.make_heap([694, 1054, 2121, 4, 878])
h.pop_heap()
Where comp is a lambda of:
comp = lambda a, b: a >= b
And I get the correct output.
However, if I pass lambda that represents the comp function in the C++ file, I get a completely different output to the C++ implementation. For example, my C++ file looks like:
#include <iostream> // std::cout
#include <algorithm> // std::make_heap, std::pop_heap, std::push_heap, std::sort_heap
#include <vector> // std::vector
bool comp (int i,int j) { return (i >= j); }
int main () {
int myints[] = {694 ,1054, 2121 ,4, 878};
std::vector<int> v(myints,myints+5);
std::make_heap (v.begin(),v.end());
std::pop_heap(v.begin(), v.end(), comp);
for (unsigned i=0; i<v.size(); i++)
std::cout << ' ' << v[i];
return 0;
}
And outputs:
694 1054 878 4 2121
And my Python file looks like:
comp = lambda a, b: int(a) >= int(b)
h = Heap()
h.make_heap([694, 1054, 2121, 4, 878])
h.pop_heap(comp)
And puts out:
[1054, 878, 694, 4, 2121]
Where have I gone wrong?