優先隊列，在哪裏插入？

所以我無法實現優先隊列。對於優先級隊列，我需要找到第一個空的位置......這是元素去的地方，我們稍後會交換..但是我很難找出找到它的算法。優先隊列，在哪裏插入？

這是我到目前爲止有：

void pq_insert(struct tnode* p) 
{ 
    struct tnode* curr=NULL; 
    struct tnode* prev=NULL; 
    printf("inserting:%c,%f\n",p->symbol,p->freq); 
    if(qhead==NULL) /*qhead is null*/ 
    { 
    qhead = p; 
     /*TODO: write code to insert when queue is empty*/ 
    } 
    /*TODO: write code to find correct position to insert*/ 
    curr = qhead; 
    while (curr != NULL){//I think this is wrong 
     if ((curr -> left) == NULL){ 
      curr = curr -> right; 
     } 
     else{ 
      curr = curr -> left; 
     } 
    } 

    if(curr==qhead) 
    { 
     /*TODO: write code to insert before the current start*/ 

    } 
    else /*insert between prev and next*/ 
    { 
     /*TODO: write code to insert in between*/ 
    } 
}

來源

2010-01-24 SuperString

是的，你覺得代碼是錯誤的：

while (curr != NULL){//I think this is wrong 
    if ((curr -> left) == NULL){ 
     curr = curr -> right; 
    } 
    else{ 
     curr = curr -> left; 
    } 
}

是錯誤的。無論您當前的節點如何，您都可以將curr導航到樹的某個部分。

你可能想改變你的內心，如果以這樣的：

if (p->freq < curr->freq)

來源

2010-01-24 08:30:04

我想我只是找到第一個空的節點，這是最接近根和最左邊。我不認爲頻率實際上很重要？ – SuperString 2010-01-24 08:39:53

這不是優先隊列嗎？如果你不保留這個列表的排序，當你得到一個項目時，你將不得不檢查每個項目以找到正確的元素。 – 2010-01-31 01:52:24

我不知道你這個while循環做什麼。

while (curr != NULL){//I think this is wrong 
    if ((curr -> left) == NULL){ 
     curr = curr -> right; // Why to go right here?!, isn't this an empty node? 
    } 
    else{ 
     curr = curr -> left; 
    } 
}

如果我尋找最近的空（NULL）離開節點，我將在

while (curr != NULL){ 
    if ((curr -> left) == NULL){//The left node is NULL. Great, I found empty node. 
     curr = NULL; 
    } 
    else{ //hmmm, left node is not empty. Lets go left for more nodes. 
     curr = curr -> left; 
    } 
}

但是像這樣，搜索將前往左只能做。在一些插入之後，樹不會被平衡。

如果您提供更多詳細信息，則會更清楚。

來源

2010-01-24 15:25:57 Yousf

優先隊列，在哪裏插入？

回答

相關問題