1

ヒープが配列に基づいており、ルートが抽出されている場合、私が使用しているコードは、ヒープ プロパティが維持されるようにノードを再シャッフルすることを想定しています。

私の理解では、配列とヒープはまったく同じではありませんが、コードでは、ヒープを構築することは、ヒープ プロパティを保持するように配列を再配置するだけのようです。これはヒープを作成する標準的な方法ですか? ベースとなる配列を変更するだけでなく、別の配列を埋める必要がありますか?

function を使用してルートを削除するとextract-max、配列から要素をポップしない限り、配列は同じサイズのままであるため、この概念を理解するのに苦労しています。ヒープは小さいはずですが、ルートを置き換えるために上に移動したノードが配列内でゼロで示され、削除されないだけです。

ヒープが基本的にヒープ プロパティに従う配列である構造を保持する場合、ヒープの一部ではなくなったノードを削除するにはどうすればよいですか? 私のコードでは、このノードは0、配列を印刷するときに a で示されます。

#include <iostream>
#include <deque>
#include "print.h"
#include "random.h"

int parent(int i)
{
    return (i - 1) / 2;
}

int left(int i)
{
    if(i == 0)
        return 1;
    else
        return 2*i;
}

int right(int i)
{
    if(i == 0)
        return 2;
    else
        return 2*i + 1;
}

void max_heapify(std::deque<int> &A, int i, int heapsize)
{
    int largest;
    int l = left(i);
    int r = right(i);
    if(l <= heapsize && A[l] > A[i])
        largest = l;
    else
        largest = i;
    if(r <= heapsize && A[r] > A[largest])
        largest = r;
    if(largest != i) {
        exchange(A, i, largest);
        max_heapify(A, largest, heapsize);
    }
}

void build_max_heap(std::deque<int> &A)
{
    int heapsize = A.size() - 1;
    for(int i = (A.size() - 1) / 2; i >= 0; i--)
        max_heapify(A, i, heapsize);
}

int heap_extract_max(std::deque<int> &A, int heapsize)
{
    if(heapsize < 0)
        throw std::out_of_range("heap underflow");
    int max = A.front();
    //A.pop_front();
    A[0] = A[heapsize--];
    //A.pop_back();
    max_heapify(A, 0, heapsize);
    return max;
}

int main(int argc, const char * argv[])
{
    std::deque<int> B = deq(7);
    print(B);
    build_max_heap(B);
    print(B);
    std::cout << "Extract max ->\t" << heap_extract_max(B, B.size()) << std::endl;
    print(B);
    std::cout << "Extract max ->\t" << heap_extract_max(B, B.size()) << std::endl;
    print(B);
    return 0;
}

出力：

79 92 86 29 27 42 6 
92 86 79 29 27 42 6 
Extract max ->  92
86 79 42 29 27 0 6 
Extract max ->  86
79 42 27 29 0 0 6
4

2 に答える 2

0

そう。max-heapify排除すべきノードへのインデックスを返すように変更しました。

int max_heapify(std::deque<int> &A, int i, int heapsize)
{
    int largest;
    int l = left(i);
    int r = right(i);
    if(l <= heapsize && A[l] > A[i])
        largest = l;
    else
        largest = i;
    if(r <= heapsize && A[r] > A[largest])
        largest = r;
    if(largest != i) {
        exchange(A, i, largest);
        int j = max_heapify(A, largest, heapsize);
        return j;
    }
    return i;
}

次に、要素を消去しましたheap_extract_max

int heap_extract_max(std::deque<int> &A, int heapsize)
{
    if(heapsize < 0)
        throw std::out_of_range("heap underflow");
    int max = A.front();
    A[0] = A[heapsize--];
    int i = max_heapify(A, 0, heapsize);
    A.erase(A.begin() + i);
    return max;
}

11 個の要素に対して次の出力が得られます。

79 10 61 99 28 12 51 96 13 37 83 
99 96 83 79 37 61 51 10 13 28 12 
Extract max ->  99
96 83 61 79 37 12 51 10 13 28 
Extract max ->  96
83 79 61 51 37 12 10 13 28

最初は、値がルートに記録された後に最後の要素をポップしてヒープを再編成できると本当に思っていましたが、うまくいきませんでした。そのため、代替手段は、ヒープが再編成された後にノードの位置を削除することでした。

元のコードに戻ります。

どこに問題があるのか​​が分かりました。後ではなく、変数を使用して配列にインデックスを付ける前に、ヒープサイズをデクリメントする必要があります。次に、意図したとおりに最後の要素をポップできます。

int heap_extract_max(std::deque<int> &A, int heapsize)
{
    if(heapsize < 0)
        throw std::out_of_range("heap underflow");
    int max = A.front();
    A[0] = A[--heapsize];
    A.pop_back();
    max_heapify(A, 0, heapsize);
    //int i = max_heapify(A, 0, heapsize);
    //A.erase(A.begin() + i);
    return max;
}
于 2013-09-24T22:05:21.213 に答える
0

関数heap_extract_maxは の最後の要素を破棄していstd::dequeます。

int heap_extract_max(std::deque<int> &A, int heapsize)
{
    if(heapsize < 0)
        throw std::out_of_range("heap underflow");
    int max = A.front();  // Get a copy of the first element
    A[0] = A[heapsize--]; // Copy the last element to the first element
                          // and reduce the heap size, effectively 
                          // discarding the last element.
    max_heapify(A, 0, heapsize);
    return max;
}

pop_back()この後、必要に応じて onを安全に使用してstd::deque、コンテナーからその要素を削除できます。

于 2013-09-24T22:08:55.703 に答える