Understanding pop_heap in C++ for implementation in Python

Viewed 281

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?

1 Answers

C++ uses less-than comparison functions:

bool comp (int i,int j) { return (i >= j); }

should be:

bool comp (int i,int j) { return (i < j); }
Related