了解 C++ 中的 pop_heap 以便在 Python 中实现

Question

我不得不将一些 C++ 代码转换为 Python 以进行部署，目前正在努力实现 C++ STL 堆数据结构。

我目前在 Python 中实施了以下 class：

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

为了测试功能，我编写了以下 C++ 文件：

// 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;
}

现在如果我运行:

std::pop_heap(v.begin(), v.end());

我得到：

1054 878 694 4 2121

如果我在 Python 中尝试使用：

if __name__ == "__main__":
    h = Heap()
    heap.make_heap([694, 1054, 2121, 4, 878])
    h.pop_heap()

其中 comp 是以下的 lambda：

comp = lambda a, b: a >= b

我得到了正确的输出。

但是，如果我在 C++ 文件中传递表示 comp 函数的 lambda，我将得到与 C++ 实现完全不同的输出。例如，我的 C++ 文件如下所示：

#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;
}

并输出：

 694 1054 878 4 2121

我的 Python 文件如下所示：

    comp = lambda a, b: int(a) >= int(b)

    h = Heap()
    h.make_heap([694, 1054, 2121, 4, 878])

    h.pop_heap(comp)

并输出：

[1054, 878, 694, 4, 2121]

我哪里做错了？

Answer 1

C++ 使用小于比较函数：

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

应该是：

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

了解 C++ 中的 pop_heap 以便在 Python 中实现

Understanding pop_heap in C++ for implementation in Python

c++

python

heap