樹和優先級隊列

我試圖解決一個練習，結果有點困難，因爲我必須實現從樹的一個模板類（一種紅黑色或二進制搜索樹）開始的優先級隊列。樹和優先級隊列

使用它看起來像

class Node 
    int key 
    Node left 
    Node right 
    Node parent 
    int leftNodes 
    int rightNodes

最初模板，當我不得不插入一個新元素我試圖填充樹的完全的水平，然後使用InOrderTreeTRaversal /排序算法填充陣列，並且生成一個來自該數組的BinarySearch樹，並用新的根元素替換原始元素。假設有一棵平衡的樹。

不幸的是，因爲樹必須效仿保持平衡樹，每次插入/缺失maxheap財產（和我的代碼沒有完全中填充樹級別不錯的選擇）此方法似乎不合適。有可能實現具有Heap功能的Tree？我的意思是每個元素都是大於或等於它的子元素的樹，在插入後保持平衡並在根節點（較大的關鍵元素）被刪除時具有自動平衡功能？

2013-05-16 Daved

[紅黑樹]（http://en.wikipedia.org/wiki/Red%E2%80%93black_tree）是你在找什麼。 –

使用RedBlack Tree可以在樹上使用按值排序的元素？在添加或刪除導致混亂的樹時反轉結構。我需要在根級別和級別級別節點上的最大元素小於或等於其父級。 – Daved

你可能想實現二進制堆，看到這個數據結構的主要優點http://en.wikipedia.org/wiki/Binary_heap

IIRC之一是，它可以嵌入到一個數組（因爲平衡的性質）。 Heapsort使用這種數據結構就地排序。

2013-05-17 04:44:23

是的，它是真的，purpouse是設計一個像二進制堆。但不是用於存儲節點的數組，我必須使用答案中提供的類節點。 – Daved

對不起，感到困惑。鏈接的維基百科文章描述了樹形的算法，請參閱「插入」和「刪除」部分。嵌入到數組中僅僅是一個與此不相關的優化（但它有助於此數據結構的重要性）。 –

回答