一道java面試題，20億數(shù)字的文本排序，如何取前100？因?yàn)檫@是一個(gè)Java問題，所以這是典型的TOPK問題。首先取前100個(gè)數(shù)字構(gòu)建一個(gè)最小堆，然后依次從堆的頂部插入剩余的數(shù)字，同時(shí)調(diào)整堆。堆中最

一道java面試題，20億數(shù)字的文本排序，如何取前100？

因?yàn)檫@是一個(gè)Java問題，所以這是典型的TOPK問題。首先取前100個(gè)數(shù)字構(gòu)建一個(gè)最小堆，然后依次從堆的頂部插入剩余的數(shù)字，同時(shí)調(diào)整堆。堆中最后100個(gè)元素就是結(jié)果。空間復(fù)雜度為k，時(shí)間復(fù)雜度為nlogk

顧名思義，即堆的每個(gè)節(jié)點(diǎn)都大于其后代，稱為大根堆，堆的每個(gè)節(jié)點(diǎn)都小于其左右后代，稱為小根堆。

最大堆和最小堆原理？

最大堆和最小堆是指堆的頂部分別有最大或最小元素的堆，也稱為大頂堆和小頂堆。堆是一種基本的抽象數(shù)據(jù)類型，通常用二叉樹表示并遞歸定義。堆的頂部是樹的根，這確保樹或子樹的根始終大于或小于子節(jié)點(diǎn)。優(yōu)先級(jí)隊(duì)列是堆的一個(gè)實(shí)例。使用最大堆還是最小堆取決于實(shí)際情況和個(gè)人定義。cqueue的STL中的容器優(yōu)先級(jí)實(shí)現(xiàn)了優(yōu)先級(jí)隊(duì)列，默認(rèn)為big top heap。