堆是我們一個(gè)常用的數(shù)據(jù)結(jié)構(gòu)，堆是一個(gè)完全二叉樹，下圖是一個(gè)小根堆，小根堆的意思是對(duì)于樹里面的所有節(jié)點(diǎn)，都是父節(jié)點(diǎn)小于任何一個(gè)子節(jié)點(diǎn)，今天創(chuàng)新互聯(lián)來(lái)看一下Go中是怎么實(shí)現(xiàn)堆？

下面是Go語(yǔ)言中實(shí)現(xiàn)一個(gè)堆的代碼，對(duì)于每一個(gè)堆，我們都需要實(shí)現(xiàn)5個(gè)方法，這點(diǎn)感覺比Java的優(yōu)先隊(duì)列要復(fù)雜得多了，分別是Len，用來(lái)計(jì)算容器得長(zhǎng)度，Less返回兩個(gè)元素得大小關(guān)系，Swap，用來(lái)交換兩個(gè)數(shù)據(jù)。這幾個(gè)實(shí)際上都是用來(lái)實(shí)現(xiàn)sort接口的。接下來(lái)，我們需要實(shí)現(xiàn)Push跟Pop方法，對(duì)于一個(gè)以前不是寫Go語(yǔ)言的人，可能覺得這個(gè)實(shí)現(xiàn)其實(shí)很冗余，Push方法我們要做的就是往數(shù)據(jù)結(jié)構(gòu)的最后面插入一個(gè)元素，而Pop則是彈出一個(gè)元素，彈出元素則是簡(jiǎn)單的把最后一個(gè)元素取出來(lái)。小根堆不是最前面的元素才是最小的么？為什么是取最后一個(gè)元素？

我們看一下go語(yǔ)言中，heap的源碼，堆需要你實(shí)現(xiàn)Push跟Pop接口，因?yàn)槔^承了sort接口，所以又要實(shí)現(xiàn)上面3個(gè)比較方法。

下面則是sort的接口，要求你實(shí)現(xiàn)長(zhǎng)度，小于跟交換。

接下來(lái)則是堆里面的push操作，先是調(diào)用了你實(shí)現(xiàn)的往末尾添加一個(gè)元素的接口，然后執(zhí)行up操作，維護(hù)小根堆。up操作的目的是為了保證小根堆里面每一個(gè)結(jié)點(diǎn)都比子節(jié)點(diǎn)小。

剛剛我們提出一個(gè)疑問(wèn)，小根堆不是最前面的元素才最小么？這里堆里面的Pop方法是先把最小的元素放到最后面，然后再來(lái)維護(hù)這個(gè)長(zhǎng)度減一的小根堆。所以實(shí)際上你上面執(zhí)行方法的時(shí)候，最后一個(gè)元素才是最小的！

這里不由感嘆，還是Java的PriorityQueue封裝的好，使用起來(lái)更加方便。雖然很多人特別推崇Go，但我覺得每種語(yǔ)言都有各自的優(yōu)點(diǎn)缺點(diǎn)，都說(shuō)Go寫起來(lái)很方便，這不，還是Java大法好。

網(wǎng)頁(yè)名稱：Go語(yǔ)言中怎么實(shí)現(xiàn)一個(gè)小根堆，Java程序員表示看懵了
標(biāo)題URL：http://jinyejixie.com/news44/98144.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供Google、移動(dòng)網(wǎng)站建設(shè)、虛擬主機(jī)、網(wǎng)站導(dǎo)航、網(wǎng)站排名、軟件開發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)