K-D yığını - K-D heap

20 öğeli 2 boyutlu bir yığın.

Bir K-D yığını^[1] bir veri yapısı içinde bilgisayar Bilimi çok boyutlu bir öncelik sırası ek alan gerektirmeden. Bu bir genellemedir Yığın.^[2] K boyutlarından herhangi birinde etkin bir şekilde yerleştirmeye, minimum öğenin sorgulanmasına ve minimum öğenin silinmesine izin verir ve bu nedenle, çift ​​uçlu yığın özel bir durum olarak.

Yapısı

Bir koleksiyon verildiğinde n her birinin sahip olduğu öğeler ${ displaystyle k}$ anahtarlar (veya öncelikler), K-D yığını bunları bir ikili ağaç iki koşulu karşılar:

• Bu bir tam ikili ağaçBu, soldan doldurulması gereken muhtemelen son katman dışında dolu olduğu anlamına gelir.
• Tatmin ediyor k-d yığın sırası.

Mülkiyet k-d yığın sırası şununkine benzer yığın özelliği düzenli yığınlar için. Bir yığın, aşağıdaki durumlarda k-d yığın sırasını korur:

• Kökteki düğüm, tüm ağacın en küçük 1. özelliğine sahiptir ve
• Diğer her düğüm v bu kök değil, öyle ki ebeveyni w alt ağacın en küçük i-inci özelliğinin kökeni ebeveyn tarafından ise v en küçüğüne sahip ${ displaystyle (i mod k) +1}$köklü tüm alt ağacın -th özelliği v.

Bu yapının bir sonucu, en küçük 1. özellik elemanının önemsiz bir şekilde kökte ve dahası en küçüğünün de kökte olmasıdır. benher biri için özellik öğeleri ben ilk olacak k seviyeleri.

Operasyonlar

Bir K-D yığını oluşturma n öğeler alır O (n) zaman. Aşağıdaki işlemler desteklenmektedir:

• Zamanında yeni bir öğe ekleyin O (log n)
• Herhangi bir boyutta minimum anahtarla öğeyi sabit zamanda geri alın
• Herhangi bir boyutta minimum anahtara sahip bir öğeyi zaman içinde silme O (log n)
• Yığın içindeki rastgele bir öğeyi zamanında silin veya değiştirin O (log n) Yığın içindeki konumunu bilindiğini varsayarsak

Daha da önemlisi, bu işlemlerde gizli sabit katlanarak büyük göreceli ${ displaystyle k}$, boyutların sayısı, dolayısıyla K-D yığınları çok fazla boyutlu uygulamalar için pratik değildir.

Referanslar