Min HL kullanarak STL Önceliği Sırası açıklaması

Question

C++ 'da oldukça yeni ve C++' da Priority Queue STL kullanarak Min Heap uygulamasına çalışıyorum. Web'in etrafına baktım ve altta eklediğim bağlantı olan bir kod üzerinde değişiklik yaptım.

Vektörlerin nasıl çalıştığını ve bir nabzın ne olduğunu anladığımı anlıyorum, ancak 'i' j 'öğesinin öğeleri minimumdan maksimum düzeye ayarlamasında nasıl bir rol oynadığını anlayamıyorum.

Kodu burada yayınlayacağım.

#include <queue> 
#include <iostream> 

using namespace std; 

struct comparator { 
    bool operator()(int i, int j) { 
    return i > j; 
    } 
}; 

int main(int argc, char const *argv[]) 
{ 
    priority_queue<int, std::vector<int>, comparator> minHeap; 

    minHeap.push(10); 
    minHeap.push(5); 
    minHeap.push(12); 
    minHeap.push(3); 
    minHeap.push(3); 
    minHeap.push(4); 

    while (!minHeap.empty()) { 
    cout << minHeap.top() << " "; 
    minHeap.pop(); 
    } 
    return 0; 
} 

Birisi programın yürütülmesini izleyebilir mi? Bu programın geçen birkaç saat boyunca şanssız olarak nasıl çalıştığını anlamaya çalışıyorum.

Ben belirli bir kritere göre, birinci öğe her zaman içerdiği elementlerin en fazla olduğu here

Answer 1

Öncelik sıralardan kodu var. Bu kriter sizin functor comparator. Bu durumda, verilen iki unsur için minör olanın ilk olması gerektiğini tanımlar. Biz tüm unsurları ayıklamak eğer

Dolayısıyla, kodunuzda, çıkış olacak eleman maks min sipariş:

while (!minHeap.empty()) { 
    cout << minHeap.top() << " "; 
    minHeap.pop(); 
} 
//output: 3,3,4,5,10,12 

algoritması bir eleman bir yığın gibidir itmek:

1. Yeni öğeyi dizideki bir sonraki kullanılabilir konuma yerleştirin. (ağacın alt seviyesi)
2. Yeni elemanı, sağlanan çeviriciyi kullanarak (comparator) üst öğe ile karşılaştırın. Bu durumda, karşılaştırma " yeni öğe daha küçükse", sonra üst öğeyle birlikte değiştirin.
3. ya kadar bu işleme devam:
   • yeni öğenin üst daha küçük ya da yeni elemanına eşittir ya da
   • yeni elemanı kök
   ( dizi indeksi 0) ulaşır

Belki algoritma görsel örnekle nasıl çalıştığını görmek için daha fazla açık: zaten sayılar 6,3,5,9 itti var düşünün ve şimdi itin 2.