Matlab中的heapsort

Question

嘿傢伙。我試圖在Matlab中編寫一個用於heapsort的算法。它不工作。堆正在建設好。填充排序的向量不起作用。這是代碼，謝謝！

function [xs,h]= heap(x) 
N = length(x); 
h = zeros(1,N); 
N_h = 0; 
for i=1:N 
    N_h = N_h +1; 
    child = N_h; 
    h(child) = x(i); 
    while child>1 
     parent = floor(child/2); 
     if h(child)>h(parent) 
      tmp = h(parent); 
      h(parent) = h(child); 
      h(child) = tmp; 
      child = parent; 
     else 
      break 
     end 
    end 

end 
xs = zeros(1,N); 
    parent = 1; 

for i = N:-1:1 
    xs(i) = h(1); 
    h(1) = h(i); 

    child1 = 2*parent; 
    child2= 2*parent+1; 

    if child1 <= i-1 


     if h(child1)>h(child2) 
      cchild = child1; 
     else 
      cchild = child2; 
     end 

     if h(parent) < h(cchild) 
      tmp = h(parent); 
      h(parent) = h(child); 
      h(child) = tmp; 
      parent = child; 
     else 
      break 
     end 

    end 

end 

Answer 1

您的提取物 - 第一項編碼是錯誤的（你可能猜到了，因爲它是不工作:-)位） - 它看起來像你做循環的唯一一個步驟中，您需要。你需要用堆中的「last」元素替換樹的根（你正在做這件事），然後沿着樹從樹上移動到修復堆屬性的葉子上（你只需要做一步那）。

此外，你初始化「父」堆大跌眼鏡的外循環;除非我完全誤解了你想要做的事情，你想在每次提取元素時將其重置爲1。