哈夫曼思考

我們來(lái)看一個(gè)簡(jiǎn)單的問(wèn)題，從小到大我們面臨了很多的考試，小學(xué)-初中-高中… 然后老師對(duì)學(xué)生是如何進(jìn)行區(qū)分的呢，不能說(shuō)你考85他考73而讓老師記住每個(gè)人的分?jǐn)?shù)，而是通過(guò)一種分段的方法劃分不同的學(xué)生：

if (sum < 60) {
      result = "不及格";
  } else if (sum < 70) {
      result = "及格";
  } else if (sum < 80) {
      result = "中等";
  } else if (sum < 90) {
      result = "良好";
  } else {
      result = "優(yōu)秀";
  }

通過(guò)劃分及格片段，就可以把數(shù)以萬(wàn)計(jì)的學(xué)生分為5類(lèi)，老師只用知道這個(gè)學(xué)生是哪個(gè)類(lèi)別就大概知道他的分?jǐn)?shù)，如此就很方便管理。

我們用二叉樹(shù)來(lái)展示這個(gè)判斷過(guò)程如下：

image.png

我們永遠(yuǎn)是第一個(gè)判斷這個(gè)學(xué)生是不是不及格，然后再去判斷及格等等，那么問(wèn)題來(lái)了，一個(gè)學(xué)校的學(xué)生中如果大部分都是不及格的，這個(gè)方法就很高效，但是很顯然，我們大部分人應(yīng)該集中在中等這個(gè)范圍，所以基于此我們這個(gè)算法就有了優(yōu)化的地方。

我們需要知道每個(gè)分?jǐn)?shù)段都有多少人，大概是這樣

image.png

肉眼可見(jiàn)，70-79之間的人數(shù)是最多的，所以我們最先遍歷 70 的條件，很大可能第一次就找到結(jié)果而不用多次判斷，所以這個(gè)優(yōu)化后的二叉樹(shù)應(yīng)該是從根到葉子是權(quán)值逐漸變小的，所以他的思路就是從葉子開(kāi)始葉子都是集中找目前最小的兩個(gè)權(quán)值作為左右子樹(shù)合并為一個(gè)父節(jié)點(diǎn)以此類(lèi)推，直到找到根節(jié)點(diǎn)即可。