Öbek oluştururken benzersiz bir yığın mı?

Question

Yığın ayırma yığın & çalışıyorum.
Bir dizi var:
Yığını, kod ve kalem kullanarak oluşturmaya çalışırken, iki çeşit yığınla karşı karşıya.

kodu kullanarak, MaxHeap: 11 9 7 6 8 3 2 1

ekleme teorisi kullanılarak, MaxHeap: 11 9 7 8 6 3 2 1

i' kodu

int[] DoHeapSort(int[] value) { 
    int length = value.length; 

    for (int i = length/2; i > 0; i--) { 
     maxHeapify(value, i, length); 
    } 

    //print Heap 
    for(int i = 0 ; i<value.length; i++) 
     System.out.println(value[i]); 

    return (value); 
} 


void maxHeapify(int[] array, int index, int heapSize) { 
    int left = index * 2; 
    int right = left + 1; 
    int max = index; 

    if (left <= heapSize && array[left - 1] > array[index - 1]) { 
     max = left; 
    } 

    if (right <= heapSize && array[right - 1] > array[max - 1]) { 
     max = right; 
    } 

    if (max != index) { 
     swap(array, index - 1, max - 1); 
     maxHeapify(array, max, heapSize); 
    } 
} 

Teori, bu durumda, yığın için bir dizi oluşturmak ve sırayla 11 6'dan eklemek: kullanıyorum. (Öte yandan, kod yerindedir)

Her iki maxHeap sonucu yığın tanımını tatmin eder. Öyleyse Heap eşsiz değil mi? Teşekkürler

Answer 1

Doğru. Yığın kısıtlaması (çocukların ebeveynlerinden büyük olmadıklarıdır) yığının tamamını belirtmez, dolayısıyla genellikle birden fazla olası düzenleme vardır.

Answer 2

{1, 2, 3} öğelerini dikkate alın. Bunlardan

3    3 
/ \  / \ 
1  2  2  1 

{3, 1, 2}  {3, 2, 1} 

Hem geçerli bir maks-yığın için gerekli şartlar Karşılamanız: maksimum-yığın için iki geçerli düzenlemeler vardır.

Tam bir yığın (yani, tüm düzeyler dolu) verildiğinde, herhangi bir düğümün alt öğelerini değiştirebilir ve yine de geçerli bir yığınınız olabilir. Veya daha genel olarak, şekil özelliğini koruduğunuz sürece herhangi bir düğümün alt öğelerini değiştirebilirsiniz.

"Çocukları değiştir" ifadesinin, o alt öğeye sabitlenmiş tüm alt ağaçların yerini alması anlamına geldiğini unutmayın.

Çocukları değiştirmeye ek olarak, düğümleri yeniden düzenleyebilirsiniz.

örneğin, bu maksimum-yığın göz önünde bulundurun:

 10 
    / \ 
    9  8 
/\ /\ 
7 6 5 4 

son seviye düğümleri sırası önemli değildir; Yaprak düğümlerinden herhangi biri 8 veya 9'luk bir çocuk olabilir. Bu dört çocuğun 24 olası permütasyonu vardır.

Diğer düzenlemeler de mümkündür. Örneğin: {10,9,6,7,8,5,4}.

Elde ettiğiniz düzenleme, ekleme ve çıkarma algoritmalarınızın özelliklerine ve ayrıca ekleme ve çıkarma sırasına bağlıdır. Ya da, bir diziden (yani O (n) yönteminden) bir yığın oluşturmak durumunda, başladığınızda dizideki öğelerin sırası.