二进制最小堆数据结构的实现

Question

您认为这段代码有什么问题，如何改进呢？我忽略了哪个角落的案子，如果有的话？

注意:我不想在这里使用任何STL特性，但是我不介意C++11中的任何其他特性。

class min_heap{
    int pvt,P;
    int arr[10000];
public:

    min_heap(){
        P=1;
    }
    void add(int x){
        pvt=P;
        arr[P]=x;

        while(pvt>1){
            if(arr[pvt]<arr[pvt/2]){
                int temp=arr[pvt];
                arr[pvt]=arr[pvt/2];
                arr[pvt/2]=temp;
                pvt=pvt/2;

            }
            else
                break;
        }
        P++;
    }

    int extract(){
        int ans=arr[1];
        arr[1]=arr[P-1];
        int elm=arr[1];
        int x=1;
        while(x*2+1<=P-1){
            int exc=1;
            int temp=arr[x];

            if(arr[x*2]>arr[x*2+1]&&(elm>arr[x*2]||elm>arr[x*2+1])){
                arr[x]=arr[x*2+1];
                arr[x*2+1]=temp;
                x=x*2+1;
                continue;
            }
            if(arr[x*2]<=arr[x*2+1]&&(elm>arr[x*2]||elm>arr[x*2+1])){
                arr[x]=arr[x*2];
                arr[x*2]=temp;
                x=x*2;
                continue;
            }
            break;

        }
        if(P-1>=x*2&&arr[x*2]<arr[x]){
            int temp=arr[x];
            arr[x]=arr[x*2];
            arr[x*2]=temp;
        }
        P--;
        return ans;
    }
};


int main()
{
    min_heap min1;
    for(int i=1;i<=50;i++)
    {
        int x1;
        std::cin>>x1;
        min1.add(x1);
    }
    std::cout<<std::endl;
    for(int i=1;i<=50;i++){
        int x1=min1.extract();
        std::cout<<x1<<std::endl;
    }


}

Answer 1

你已经说过你不想使用STL，所以我会尊重这一点。请注意，忽略使用它可能会降低代码的质量，特别是当您开始体验bug时。

我将主要讨论最佳实践，因为我自己对算法不太熟悉。

• 你缺少空白只会让你读起来很痛苦。如果一行看起来太长，则需要缩短(首选)或包装在单独的行上。无论哪种方式，您特别应该在操作符和操作数之间有一些空格，这样就不会占用其他人不必要的时间来阅读和理解它。这也将使您在维护代码时受益(修复bug、添加内容和更改代码)。例如，这一行: if(arrX*2>arrX*2+1&&(elm>arrX*2||elm>arrX*2+1)){应该如下所示: if (arrX*2 > arrX*2+1 && (elm > arrX*2而青elm >arrX*2+1){这不是更容易读懂吗？没有必要把所有的东西都塞在一起，只要让代码呼吸就行了。您仍然可以在[]中划分操作符，但并不是很常见。
• 您的变量名是非常通用的。其中许多只有一个字母，您的数组数据成员只是命名为arr。如果没有好的命名，您只会让其他人猜测每个变量的作用。另外，如果您从现在开始看这段代码，您可能不知道这一切意味着什么，因此您可能会忍不住扔掉它，重新开始。
• 尽管它完全是可选的，但是您仍然可以添加private关键字，即使默认情况下classes是private。它可能会增加一些可读性，特别是如果有大量的代码。
• 构造函数: min_heap(){ P=1；}可以是初始化程序列表：min_heap()：P(1) {}，如果它变得冗长，您可以在单独的行上列出成员: min_heap()：P(1)，// P=1，//用逗号{}分隔，如果需要初始化pvt和arr，那么也应该在这里完成。我不知道你为什么要初始化一个数据成员。
• 你不需要std::endl在这里。在大多数情况下，同花顺和换行符都是不必要的，而换行符就是这样做的。相反，只需输出换行符的"\n"：std::cout << "\n"；这也提到了这里。

总的来说，我强烈建议首先使它更具可读性，这样您和其他人就更容易理解和改进。自己实现所有的算法将特别要求代码是干净的和自文档化的，否则您实际上只是在编写C代码。

Answer 2

1. 你们的名字。坦率地说，pvt很穷，P的名字也很糟糕。我仍然不知道P到底是什么意思。
2. 您已经使用了一个固定大小的数组，但它并不适合。如果堆包含的项少于10000项，则会浪费空间。如果用户试图添加超过10000项，它们会溢出您所分配的空间，从而导致未定义的行为。更好地使用(例如)一个std::vector，它将根据需要增长分配以接近实际使用中的大小。
3. 编写您自己的代码来交换条目: int temp=arrX；arrX=arrX*2；arrX*2=temp；...is几乎没有使用std::swap来完成任务那么有表现力。我发现std::swap(arr[x], arr[x*2]);的可读性更强。如果您希望支持使用专门的swap，以防用户为所存储的类型提供了一个这样的成语，您可以使用这样的成语:使用std:: swap；交换(arrX，arrX*2)；这样，如果存在用于arr[x]类型(定义在与该类型相同的名称空间中)的swap，则可以通过Koenig查找并用于交换。如果不存在这种情况，那么std::swap就会因为using声明而被找到。
4. 您当前的代码仅限于将ints存储在堆中，没有什么特别好的理由。对于堆的唯一真正要求是，项必须满足严格的弱排序(您必须能够比较它们，并且比较必须是传递的，如果是a<b和b<c，则是a<c)。
5. 按照同样的思路，您可以允许用户指定用于比较项的函数/对象。这允许您只需更改比较，就可以对最小堆或最大堆使用相同的代码。
6. 好处:理想情况下，我可能更喜欢通过迭代器访问堆，这样我就可以将它与标准算法等一起使用。

基于这些，我更希望看到代码的框架如下所示：

template <class T, class cmp=std::less<T>>
class heap {
    std::vector<T> data;
public:
    heap();

    template<class Iter>
    heap(Iter b, Iter e); // construct a heap from the elements pointed to by two iterators

    void insert(T);

    T extract();
};

我可能应该注意到，T extract();在异常安全方面存在潜在的问题。我假设(暂时)正在存储的类型不会在复制/移动时抛出。如果它可以在复制/移动时抛出，那么T extract()就不会是异常安全的。问题与返回弹出值的堆栈中的pop非常相似:如果复制/移动返回项引发异常，则用户不会接收该项，但该项已经从堆中删除，因此该项丢失，无法检索。

如果T可能在复制/移动时抛出异常，则通常希望将接口更改为更类似于以下内容：

T get_min();  // just retrieves smallest item, without removing it from the heap.
void pop(); // just removes smallest item

这样用户就可以检索最小的项，如果成功，则从堆中移除最小的项。奇怪的是，他们不需要检查这种成功：

T x = myheap.get_min();
myheap.pop();

如果第一条语句抛出异常，那么第二条语句将不会执行，堆保持不变。如果第一个没有抛出，那么第二个执行时(大概)没有抛出的机会。

然而，最后一个条件提出了另一个问题:在几乎每一种情况下，您都需要一些关于至少几个操作不抛出的保证。在这种情况下，我们依赖于能够在不抛出项的情况下交换项，或者不能可靠地从堆中删除项--如果交换可能抛出，那么尝试删除某个项可能会破坏堆。