7

heapsortを使用して実装するmin-heapと、配列が最大から最小にソートされます。heapsortこれはusingの望ましい出力min-heapですか? heapそれ自体が最小から最大の構造を持っているため、ソートが完了した後に最小から最大に出力するために再度ソートするのは冗長に思えます。

コード：

#include <iostream>
#include <vector>
#include "random.h"
#include "print.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 min_heapify(std::vector<int> &A, int i, int heapsize)
{
    int smallest;
    int l = left(i);
    //std::cout << "left = " << l << std::endl;
    int r = right(i);
    //std::cout << "right = " << r << std::endl;
    if(l <= heapsize && A[l] < A[i])
        smallest = l;
    else
        smallest = i;
    //std::cout << "smallest = " << smallest << std::endl;
    if(r <= heapsize && A[r] < A[smallest])
        smallest = r;
    if(smallest != i) {
        print(A);
        exchange(A, i, smallest);
        min_heapify(A, smallest, heapsize);
    }
}
void build_min_heap(std::vector<int> &A)
{
    int heapsize = A.size() - 1;
    for(int i = (A.size() - 1) / 2; i >= 0; i--)
        min_heapify(A, i, heapsize);
}
void heapsort(std::vector<int> &A)
{
    int heapsize = A.size() - 1;
    build_min_heap(A);
    std::cout << "heapsort after buildmaxheap" << std::endl;
    print(A);
    for(int i = A.size() - 1; i > 0; i--) {
        exchange(A, 0, i);
        heapsize--;
        std::cout << "heapsize = " << heapsize << std::endl;
        min_heapify(A, 0, heapsize);
    }
}
int main()
{
    std::vector<int> B;
    fill(B, 5);
    print(B);
    heapsort(B);
    print(B);
    return 0;
}

コードからの出力:

41 65 31 41 19 
41 65 31 41 19 
41 65 19 41 31 
41 19 65 41 31 
41 19 31 41 65 
19 41 31 41 65 
heapsort after buildmaxheap
19 31 41 41 65 
heapsize = 3
65 31 41 41 19 
31 65 41 41 19 
heapsize = 2
heapsize = 1
65 41 41 31 19 
heapsize = 0
65 41 41 31 19

20 要素の出力:

41 65 31 41 19 15 72 11 78 69 37 23 29 63 75 4 5 49 75 99 
after buildmaxheap
4 5 15 11 19 23 29 41 31 69 37 41 72 63 75 65 78 49 75 99 
after sort
99 78 75 75 72 69 65 63 49 41 41 37 31 29 23 19 15 11 5 4
4

3 に答える 3

6

Order : 昇順でソートするには max-heapify を使用し、降順でソートするには min-heapify を使用します。

並べ替え: min-heapify を使用してヒープを構築しても、配列は並べ替えられません。(より弱い) min-heap プロパティのみを強制します。つまり、

A[parent(i)] <= A[i]

iルート以外のすべてのノードに対して。ヒープが構築された後、ルート (配列の左端の位置) に最小要素が含まれます。並べ替えは、要素をルートから右に繰り返し移動し、ルートで min-heapify を呼び出します (そこに残っているものの最小値をもたらします)。したがって、降順になります。

あなたが投稿しているコードは一見正しいように見えますが、そのままではコンパイルできないため、テストできません。ヒープを構築した直後に配列がソートされているように見える場合、それは偶然の一致です。より大きなテストを試してください。

于 2013-09-20T17:38:50.420 に答える
2

通常、max-heap を使用して昇順で並べ替えます。簡単だからです。max-heap を使用して、max を前面に「フロート」し、背面から並べ替えられたリストを作成します。

最小ヒープを使用して昇順で並べ替えたい場合は、逆方向に構築する必要があります。(つまり、最低は最後のインデックスです)。そうしないと、ヒープをかき回すことになります。

start 18 70 6 13 12 55 
min-heap(backwards) -> 18 70 55 13 12 6
then
swap  6 w 18 -> 6, 70 55 13 12 18 -> sink 18 -> 70 55 13 18 12
swap 12 w 70 -> 6 12, 55 13 18 70 -> sink 70 -> 55 70 18 13
swap 13 w 55 -> 6 12 13, 70 18 55 -> sink 55 -> 70 55 18
swap 18 w 70 -> 6 12 13 18, 55 70 -> sink 70 -> 70 55
swap 55 w 70 -> 6 12 13 18 55, 70 
done
于 2013-09-20T17:37:28.540 に答える