geeksforgeeks-heap sort

heap sort講解:http://www.geeksforgeeks.org/heap-sort/

測(cè)驗(yàn)

The task is to complete heapify() and buildHeap() functions which are used to implement Heap Sort.

Input:
First line of the input denotes number of test cases 'T'. First line of the test case is the size of array and second line consists of array elements.

Output:
Sorted array in ascending order.

Constraints:
1 <=T<= 50
1 <=N<= 1000
1 <=arr[i]<= 1000

Example:

Input:
2
5
4 1 3 9 7
10
10 9 8 7 6 5 4 3 2 1

Output:
1 3 4 7 9
1 2 3 4 5 6 7 8 9 10

C++

/*
Please note that it's Function problem i.e.
you need to write your solution in the form of Function(s) only.
Driver Code to call/invoke your function would be added by GfG's Online Judge.*/


/* Main function to do heap sort. This function uses buildHeap()
   and heapify()
void heapSort(int arr[], int n)  {
    buildHeap(arr, n);
    for (int i=n-1; i>=0; i--)  {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
} */
// The functions should be written in a way that array become sorted 
// in increasing order when above heapSort() is called.
// To heapify a subtree rooted with node i which is  an index in arr[]. 
// n is size of heap. This function  is used in above heapSor()
void heapify(int arr[], int n, int i)  {
      // Your Code Here
      int largest = i;
      int left = 2*i + 1;
      int right = 2*i + 2;
      
      if(left < n && arr[left]>arr[largest])
      {
          largest = left;
      }
      if(right < n && arr[right]>arr[largest])
      {
          largest = right;
      }
      
      if(largest != i)
      {
          swap(arr[i], arr[largest]);
          
          heapify(arr, n, largest);
          
      }

}
// Rearranges input array so that it becomes a max heap
void buildHeap(int arr[], int n)  { 
    // Your Code Here
    for(int i = n/2-1; i>=0; i--)
    {
        heapify(arr, n, i);
    }
}

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末蓄喇,一起剝皮案震驚了整個(gè)濱河市乱顾,隨后出現(xiàn)的幾起案子勋功,更是在濱河造成了極大的恐慌哀蘑,老刑警劉巖,帶你破解...
    沈念sama閱讀 223,002評(píng)論 6 519
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡担神,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,357評(píng)論 3 400
  • 文/潘曉璐 我一進(jìn)店門(mén)始花,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)妄讯,“玉大人,你說(shuō)我怎么就攤上這事酷宵『ッ常” “怎么了?”我有些...
    開(kāi)封第一講書(shū)人閱讀 169,787評(píng)論 0 365
  • 文/不壞的土叔 我叫張陵浇垦,是天一觀的道長(zhǎng)炕置。 經(jīng)常有香客問(wèn)我,道長(zhǎng),這世上最難降的妖魔是什么朴摊? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 60,237評(píng)論 1 300
  • 正文 為了忘掉前任默垄,我火速辦了婚禮,結(jié)果婚禮上仍劈,老公的妹妹穿的比我還像新娘厕倍。我一直安慰自己寡壮,他們只是感情好贩疙,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,237評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著况既,像睡著了一般这溅。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上棒仍,一...
    開(kāi)封第一講書(shū)人閱讀 52,821評(píng)論 1 314
  • 那天悲靴,我揣著相機(jī)與錄音,去河邊找鬼莫其。 笑死癞尚,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的乱陡。 我是一名探鬼主播浇揩,決...
    沈念sama閱讀 41,236評(píng)論 3 424
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼憨颠!你這毒婦竟也來(lái)了胳徽?” 一聲冷哼從身側(cè)響起,我...
    開(kāi)封第一講書(shū)人閱讀 40,196評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤爽彤,失蹤者是張志新(化名)和其女友劉穎养盗,沒(méi)想到半個(gè)月后,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體适篙,經(jīng)...
    沈念sama閱讀 46,716評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡往核,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,794評(píng)論 3 343
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了嚷节。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片聂儒。...
    茶點(diǎn)故事閱讀 40,928評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖丹喻,靈堂內(nèi)的尸體忽然破棺而出薄货,到底是詐尸還是另有隱情,我是刑警寧澤碍论,帶...
    沈念sama閱讀 36,583評(píng)論 5 351
  • 正文 年R本政府宣布谅猾,位于F島的核電站,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏税娜。R本人自食惡果不足惜坐搔,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,264評(píng)論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望敬矩。 院中可真熱鬧概行,春花似錦、人聲如沸弧岳。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,755評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)禽炬。三九已至涧卵,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間腹尖,已是汗流浹背柳恐。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,869評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留热幔,地道東北人乐设。 一個(gè)月前我還...
    沈念sama閱讀 49,378評(píng)論 3 379
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像绎巨,于是被迫代替她去往敵國(guó)和親近尚。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,937評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容