從堆中刪除元素

Question

我做了一堆。我很好奇，如果有什麼東西subtley錯了我的刪除功能：

int Heap::remove() { 
    if (n == 0) 
     exit(1); 

    int temp = arr[0]; 
    arr[0] = arr[--n]; 
    heapDown(0); 
    arr[n] = 0; 

    return temp; 
} 

void Heap::heapDown(int i) 
{ 
    int l = left(i); 
    int r = right(i); 
    // comparing parent to left/right child 
    // each has an inner if to handle if the first swap causes a second swap 
    // ie 1 -> 3 -> 5 
    //  3 5 1 5 1 3 

    if (l < n && arr[i] < arr[l]) 
    { 
     swap(arr[i], arr[l]); 
     heapDown(l); 

     if (r < n && arr[i] < arr[r]) 
     { 
      swap(arr[i], arr[r]); 
      heapDown(r); 
     } 
    } 
    else if (r < n && arr[i] < arr[r]) 
    { 
     swap(arr[i], arr[r]); 
     heapDown(r); 

     if (l < n && arr[i] < arr[l]) 
     { 
      swap(arr[i], arr[l]); 
      heapDown(l); 
     } 
    } 
} 

這裏是我的輸出

i1i2i3i4i5i6i7 
p 
Active heap: 7 4 6 1 3 2 5 

r 
Removed 7 
r 
Removed 6 
p 
Active heap: 5 3 4 1 2 

這裏是我的老師的輸出樣本：

p 
Active heap : 7 4 6 1 3 2 5 
r 
Removed 7 
r 
Removed 6 
p 
Active heap : 5 4 2 1 3 
s 
Heapsorted : 1 2 3 4 5 

雖然我們的輸出是完全不同的，我似乎堅持一切都離開導向的最大原則，並且對於所有節點parent> child（在任何情況下我都嘗試過）。我嘗試從頭開始這樣做，所以也許我只是在做一些非常奇怪和錯誤的事情（如果它是> O（lg n），我會認爲它是「錯誤的」，因爲刪除旨在用於堆）。我的刪除有什麼特別的「錯誤」嗎？謝謝，

http://ideone.com/PPh4eQ

Answer 1

首先，我假設你的意思是除了這個事實，你並不需要它，因爲我們有一個完整的堆管理功能在C++標準庫，包括make_heap，push_heap，pop_heap設置，甚至sort_heap。

這就是說，我想我知道你的問題是什麼。你在堆中有不必要的元素移動。它涉及的堆下來交換算法：同樣的問題是在兩個左右顯着，所以我將展示的第一個：

if (l < n && arr[i] < arr[l]) 
{ 
    swap(arr[i], arr[l]); 
    heapDown(l); 

    if (r < n && arr[i] < arr[r]) 
    { 
     swap(arr[i], arr[r]); 
     heapDown(r); 
    } 
} 

這裏的邏輯是不是最佳的最小運動。元件的「較小」的狀態被按下必須分爲兩個基本類別之一，並且不同的動作對各：

1. 的元件不小於任左邊或右邊。沒做什麼。
2. 元素小於要麼向左或向右，只交換與最大，然後壓低到只該子樹。

該列表中的＃2是您的代碼中的問題。你換一個較小的，，然後較大，如果項目<離開<沒錯。我希望這很清楚。如果你想要一個提案來解決你的邏輯問題，我可以提供一個，但是如果你明白我上面描述的內容，我想你可能會對它有所幫助。

---

擾流板

void Heap::heapDown(int i) 
{ 
    int l = left(i); 
    int r = right(i); 
    int x = 0; 

    if (l < n && arr[i] < arr[l]) 
    { 
     x = l; 
     if (r < n && arr[l] < arr[r]) 
      x = r; 
    } 

    else if (r < n && arr[i] < arr[r]) 
     x = r; 

    if (x != 0) 
    { 
     swap(arr[i], arr[x]); 
     heapDown(x); 
    } 
} 

注：;在不明顯的情況下，這是尾遞歸的定義，因此可以很容易地轉化爲簡單的迭代循環。