Çizgi Roman: "Huffman Ağacı" nedir?
Yazar | Xiao Hui
Kaynak | Programcı Xiaohui (ID: chengxuyuanxiaohui)
----- sonraki gün -----
Kavram 1: Yol nedir?
Bir ağaçta, bir düğümden diğerine geçen tüm düğümlere iki düğüm arasındaki yol denir.
Yukarıdaki ikili ağaçta, kök düğüm A'dan yaprak düğüm H'ye giden yol A, B, D, H'dir.
Kavram 2: Yol uzunluğu nedir?
Bir ağaçta, bir düğümden diğerine geçen "kenarların" sayısına iki düğüm arasındaki yol uzunluğu denir.
Halen şu anda ikili ağaç örneğini kullanarak, kök düğüm A'dan yaprak düğüm H'ye toplam 3 kenar geçti, yani yol uzunluğu 3'tür.
Kavram 3: Bir düğümün ağırlıklı yol uzunluğu nedir?
Ağacın her düğümü, farklı algoritmalarda farklı roller oynayabilen kendi "ağırlığına" (Ağırlık) sahip olabilir.
Bir düğümün ağırlıklı yol uzunluğu, ağacın kök düğümünden düğüme giden yol uzunluğunun ve düğümün ağırlığının çarpımını ifade eder.
H düğümünün ağırlığının 3 olduğunu varsayarsak, kök düğümden H düğümüne giden yol uzunluğu da 3'tür, dolayısıyla H düğümünün ağırlıklı yol uzunluğu 3 X 3 = 9 olur.
Konsept 4: Bir ağacın ağırlıklı yol uzunluğu nedir?
Bir ağaçta, tüm yaprak düğümlerinin ağırlıklı yol uzunluklarının toplamı, ağacın ağırlıklı yol uzunluğu veya kısaca WPL olarak adlandırılır.
Yine de bu ikili ağacı örnek alırsak, ağacın yol uzunluğu 3X3 + 6X3 + 1X2 + 4X2 + 8X2 = 53'tür.
Huffman ağacı 1952'de Massachusetts Teknoloji Enstitüsü'nden Dr. Huffman tarafından icat edildi. Bu ne tür bir ağaç?
Şimdi ağacın ağırlıklı yol uzunluğunu (WPL) öğrendik ve Huffman ağacı, yaprak düğümleri ve ağırlıkları belirlendiğinde en küçük ağırlıklı yol uzunluğuna sahip bir ikili ağaçtır ve buna optimum ikili ağaç da denir. .
Örneğin, ağırlıkları 1, 3, 4, 6 ve 8 olan yaprak düğümleri verildiğinde, ağırlıklı yol uzunluğunun en küçük olmasını sağlamak için ne tür bir ikili ağaç inşa etmeliyiz?
Prensip olarak, daha düşük ağırlıklı yaprak düğümlerini köklerden ve daha yüksek ağırlıklı yaprak düğümlerini köklere daha yakın tutmalıyız.
Aşağıdaki şeklin sol tarafındaki ağaç bir Huffman ağacıdır ve WPL'si 46'dır, bu önceki örnekte 53'ten daha küçüktür:
Aynı yaprak düğümlerinden oluşan birden fazla Huffman ağacı olabileceğine dikkat edilmelidir. Aşağıdaki ağaçların tümü Huffman ağaçlarıdır:
6 yaprak düğüm olduğunu varsayarsak, ağırlıklar 2, 3, 7, 9, 18, 25'dir. Bir Huffman ağacı, yani en küçük ağırlıklı yol uzunluğuna sahip ağaç nasıl yapılır?
1. Adım: Ormanı inşa edin
Her bir yaprak düğümüne bağımsız bir ağaç (yalnızca kök düğümleri olan bir ağaç) gibi davranarak bir orman oluşturuyoruz:
Yukarıdaki şekilde, sağ taraf yaprak düğümleri ormanıdır ve sol taraf, tüm yaprak düğümlerini ağırlıklarına göre küçükten büyüğe depolayan yardımcı bir kuyruktur. Yardımcı kuyruğun rolüne gelince, daha sonra göreceğiz.
Adım 2: Yeni bir ana düğüm oluşturmak için en küçük akım ağırlığına sahip iki düğümü seçin
Yardımcı kuyrukların yardımıyla, en küçük ağırlıklara sahip 2 ve 3 numaralı düğümleri bulabilir ve bu iki düğüme göre yeni bir ana düğüm oluşturabiliriz.Ana düğümün ağırlığı, bu iki düğümün ağırlıklarının toplamıdır:
3. Adım: Önceki adımda seçilen en küçük iki düğümü kuyruktan kaldırın ve yeni ana düğümü kuyruğa ekleyin Yani, kuyruktan 2 ve 3'ü silin, 5'i ekleyin ve kuyruğun artan sırasını koruyun:
Adım 4: Yeni bir ana düğüm oluşturmak için en küçük akım ağırlığına sahip iki düğümü seçin.
Bu, ikinci adımın tekrarlanan işlemidir. Geçerli kuyruktaki en küçük ağırlığa sahip düğümler 5 ve 7'dir ve yeni ana düğümün ağırlığı 5 + 7 = 12'dir:
Adım 5: Önceki adımda seçilen en küçük iki düğümü kuyruktan çıkarın ve yeni ana düğümü kuyruğa ekleyin.
Bu, üçüncü adımın tekrarlanan işlemidir, yani kuyruktan 5 ve 7'yi silin, 12 ekleyin ve yine de sıranın artan sırasını koruyun:
Adım 6: Yeni bir ana düğüm oluşturmak için en küçük akım ağırlığına sahip iki düğümü seçin.
Bu, ikinci adımın tekrarlanan işlemidir. Geçerli kuyruktaki en küçük ağırlığa sahip düğümler 9 ve 12'dir ve yeni ana düğümün ağırlığı 9 + 12 = 21'dir:
Adım 7: Önceki adımda seçilen en küçük iki düğümü kuyruktan çıkarın ve yeni ana düğümü kuyruğa ekleyin.
Bu, kuyruktan 9 ve 12'yi silmek, 21'i eklemek ve yine de kuyruğun artan sırasını korumak olan üçüncü adımın tekrarlanan işlemidir:
Adım 8: Yeni bir ana düğüm oluşturmak için en küçük akım ağırlığına sahip iki düğümü seçin.
Bu, ikinci adımın tekrarlanan işlemidir. Mevcut kuyruktaki en küçük ağırlığa sahip düğümler 18 ve 21'dir ve yeni ana düğümün ağırlığı 18 + 21 = 39'dur:
Adım 9: Önceki adımda seçilen en küçük iki düğümü kuyruktan çıkarın ve yeni ana düğümü kuyruğa ekleyin.
Bu, üçüncü adımın tekrarlanan işlemidir, yani kuyruktan 18 ve 21'i silin, 39'u ekleyin ve hala sıranın artan sırasını koruyun:
Onuncu adım: yeni bir ana düğüm oluşturmak için en küçük akım ağırlığına sahip iki düğümü seçin.
Bu, ikinci adımın tekrarlanan işlemidir. Mevcut kuyruktaki en küçük ağırlığa sahip düğümler 25 ve 39'dur ve yeni ana düğümün ağırlığı 25 + 39 = 64'tür:
Adım 11: Önceki adımda seçilen en küçük iki düğümü kuyruktan kaldırın ve yeni ana düğümü kuyruğa ekleyin
Bu, üçüncü adımın tekrarlanan işlemidir, yani kuyruktan 25 ve 39'u silin ve 64'ü ekleyin:
Şu anda, kuyrukta tüm ormanın tek bir ağaçta birleştiğini gösteren tek bir düğüm vardır ve bu ağaç, istediğimiz Huffman ağacıdır:
Bu kodda, düğüm kuyruğundaki düğümlerin her zaman artan ağırlık sırasına göre düzenlenmesini sağlamak için öncelik kuyruğu PriorityQueue kullanıyoruz.
Aynı zamanda, statik iç sınıf Node'un, Node nesnelerinin kuyruğa girdiklerinde ağırlıklarına göre karşılaştırılmalarını sağlamak için karşılaştırma arabirimini uygulaması ve CompareTo yöntemini yeniden yazması gerekir.
Zhou Hongyi tarafından tüm ağda engellenen 360 acımasız general: yüz milyonlarca net servete sahip 36 yaşındaki tabandan bir karşı saldırı!
2020'de siber güvenlikte öğrenmeye değer 5 programlama dili
10 kez HD maliyeti yok! SVG oluşturma
Microsoft bir kişi için bir şirket mi satın alıyor? Sony programlarını kırın, hacker romanları yazın ve sağlam program hayatını izleyin!
Makine öğrenimi proje şablonu: Makine öğrenimi projesinin 6 temel adımı
IBM, Microsoft, Apple, Google, Samsung ... blok zincirindeki teknoloji devleri şimdiden çok şey yaptı!
Kıdemli programcının özeti: Linux sürecini analiz etmek için 6 yöntem, size hepsini anlatacağım
Bugünün refahı: yorum alanı seçildi, çevrimiçi 299 yuan değerinde "2020 AI Geliştiricileri Konferansı" nı alabilirsiniz Bir canlı bilet . Parmaklarınızı hareket ettirin ve söylemek istediklerinizi yazın.
