優先隊列堆實現

Question

我在寫代碼來實現使用堆的優先級隊列。當我按照這個特定順序將這些優先級輸入到隊列中時8 10 4 3 7 6 9 5當我開始用get_front()函數彈出它們時，出現錯誤。

問題是while函數的swap_with_parent()函數的斷言失敗。該參數以某種方式增長得比數組中的項目數many_items大。我會發布整個代碼，如果有人可以發現一個問題，我會很感激，如果你能讓我知道。對於缺乏評論，我提前表示歉意，我希望這足夠清楚我所做的事情。

// INVARIANT for the PriorityQueue Class: 
// 1. The member variable many_items is the number of items in the 
//  PriorityQueue. 
// 2. The items themselves are stored in the member variable heap, 
//  which is a partially filled array organized to follow the usual 
//  heap storage rules from Chapter 11 of the class notes. 
// NOTE: Private helper functions are implemented at the bottom of this 
// file along with their precondition/postcondition contracts. 

#include <assert.h> // Provides assert function 
#include <iomanip> // Provides setw 
#include <iostream> // Provides cin, cout 
#include <math.h>  // Provides log2 
#include "pqueue2.h" 

using namespace std; 

PriorityQueue::PriorityQueue() 
{ 
    heap[CAPACITY]; 
    many_items=0; 
} 

void PriorityQueue::insert(const Item& entry, unsigned int priority) 
{ 
    if(many_items==0) 
    { 
     heap[many_items].data= entry; 
     heap[many_items].priority= priority; 
     many_items++; 
    } 
    else 
    { 
     heap[many_items].data= entry; 
     heap[many_items].priority= priority; 
     unsigned int i= many_items; 
     many_items++; 
     while(parent_priority(i)<priority) 
     { 
      swap_with_parent(i); 
      i=parent_index(i); 
     } 
    } 
} 

PriorityQueue::Item PriorityQueue::get_front() 
{ 
    assert(many_items>0); 
    if(many_items==1) 
    { 
     Item front_value=heap[0].data; 
     many_items--; 
     return front_value; 
    } 
    else 
    { 
     Item front_value=heap[0].data; 
     heap[0]=heap[many_items-1]; 
     unsigned int priority= heap[many_items-1].priority; 
     unsigned int k=0; 
     while((k<many_items) && !is_leaf(k) && big_child_priority(k)>priority) 
     { 
      unsigned int j=big_child_index(k); 
      swap_with_parent(big_child_index(k)); 
      k= j; 
     } 
     many_items--; 
     return front_value; 
    } 
} 

bool PriorityQueue::is_leaf(size_t i) const 
// Precondition: (i < many_items) 
// Postcondition: If heap[i] has no children in the heap, then the function 
// returns true. Otherwise the function returns false. 
{  
    if(((2*i)+1)>many_items) 
     return 1; 
    else 
     return 0; 
} 

size_t PriorityQueue::parent_index(size_t i) const 
// Precondition: (i > 0) && (i < many_items) 
// Postcondition: The return value is the index of the parent of heap[i]. 
{ 
    //assert(/*(i>0) && */(i<many_items)); 
    return (i-1)/2; 
} 

unsigned int PriorityQueue::parent_priority(size_t i) const 
// Precondition: (i > 0) && (i < many_items) 
// Postcondition: The return value is the priority of the parent of heap[i]. 
{ 
    return heap[ (i-1)/2].priority; 
} 

size_t PriorityQueue::big_child_index(size_t i) const 
// Precondition: !is_leaf(i) 
// Postcondition: The return value is the index of one of heap[i]'s children. 
// This is the child with the larger priority. 
{ 
    assert(!is_leaf(i)); 
    if((2*i)+2<many_items) 
    { 
     if(heap[(2*i)+1].priority>heap[(2*i)+2].priority) 
     { 
      return (2*i)+1; 
     } 
     else 
     { 
      return (2*i)+2; 
     } 
    } 
    else 
    { 
     return(2*i)+1; 
    } 
} 

unsigned int PriorityQueue::big_child_priority(size_t i) const 
// Precondition: !is_leaf(i) 
// Postcondition: The return value heap[big_child_index(i)].priority 
{ 
    return heap[big_child_index(i)].priority; 
} 

void PriorityQueue::swap_with_parent(size_t i) 
// Precondition: (i > 0) && (i < many_items) 
// Postcondition: heap[i] has been swapped with heap[parent_index(i)] 
{ 
    assert(i>0 && i<many_items); 
    OneItemInfo temp_parent=heap[parent_index(i)]; 
    OneItemInfo temp_child=heap[i]; 
    heap[i]=temp_parent; 
    heap[parent_index(i)]=temp_child; 
} 

Answer 1

我認爲is_leaf是不正確的。條件應該是(2*i+1 >= many_items)。