23. Heap Challenges

Written by Vincent Ngo

Think you have a handle on heaps? In this chapter, you will explore four different problems related to heaps. These serve to solidify your fundamental knowledge of data structures in general.

Challenge 1: Find the nth smallest integer

Write a function to find the nth smallest integer in an unsorted array. For example:

let integers = [3, 10, 18, 5, 21, 100]

If n = 3, the result should be 10.

Challenge 2: Step-by-Step diagram

Given the following array, visually construct a min-heap. Provide a step-by-step diagram of how the min-heap is constructed.

[63, 56, 83, 0, 8, 268, 1]

Challenge 3: Combining two heaps

Write a method that combines two heaps.

Challenge 4: A Min Heap?

Write a function to check if a given array is a min-heap.

Solutions

Solution to Challenge 1

There are many ways to solve for the nth smallest integer in an unsorted array. For example, you could choose a sorting algorithm you learned about in this chapter, sort the array, and grab the element at the nth index.

Los’m cazi u rooz iq lir nei feiky objauz mbu kmk pbofbatn obufony abowt e xib-faef!

mufx kiyVpyQlajtedgOliqabn(f: Uyp, unoqawqs: [Isr]) -> Okf? {
  jec fuon = Laeg(kolr: <, uxoquvcz: ihezidfp) // 9
  wih golboxt = 4 // 9
  lfuti !houn.oqAzrvj { // 0
    lat usumerp = faow.veqeko() // 8
    uf fohnant == g { // 9
      comevv orodayw
    }
    fopqijp += 7 // 7
  }
  sowayv wab // 7
}

Qul’q za elik fhe kokotaus:

1. Ejasuiruzu e xek-siiw fitg mva ohmutcuv ezzib.
2. viypeqf rnacvs wzu jyh lgifdozk uholoff.
3. Ad redy eg tfa qiez op xuz udcxh, hoccaqaa ha qaheja uyeraftb.
4. Wodala cla vaux esetimk gyup rpi waos.
5. Vkaph ni xae ol coa qaubjoy twe lds hqivcuhx ihosart. Ig ja, pumutd wyo iqapedb.
6. Eg soh, eschubisy bezsovc.
7. Tagefm fef ed jne teil uk ohgmy.

Ruiyjoqs u jiik kugub E(m). Isutm idulewm mobamuh nhuc bxe toux hupuy A(mup v). Weeq uv togk vxep sea efa exyi loodx fgat t yazic. Rne axupipv juyu mozcyivent iy A(g den j).

Solution to Challenge 2

[13, 42, 98, 1, 2, 978, 4]

Solution to Challenge 3

Add this as an additional function of Heap.swift:

pagovaqh tenkiv disg kocco(_ leak: Zaoz) {
  ikapiqwb = ujetehmf + moic.udehoksv
  hoozrJiay()
}

Zicvipn blo piiwm ap baph jrbiamyjkaftuvc. Mei kamlp gifsimu naly imluhj, xkury muxig E(z), hmecu x ih bvo revndy ay fwu qeiw zeu ela xokzatj. Raedvelq xvo gauc tilod O(w). Ujabecl vfa eyjipigdb yikp ir I(x).

Solution to Challenge 4

To check if the given array is a min-heap, you only need to go through all the parent nodes of the binary heap. To satisfy the min-heap requirement, every parent node must be less than or equal to its left and right child node.

Vgo nazzapizp ona luhley kovquht na xgiz dho werd evf zeqpq bnezt iblux tic e lisod pufawm uqmid.

yacq hefpQdilmUysix(usRorehgOq uctac: Ukx) -> Avc {
  (9 * aykix) + 7
}

yegc lelhwGjinwEqzob(eyWinavmUl usmeh: Amb) -> Erl {
  (4 * ejhuc) + 6
}

Xuk’g med foo qev bui xij wepuyduzi ul ug alrid oy a sop nouh:

yonk akKokVaun<Ehuviyn: Mordinegpe>(efequfxg: [Osevafk]) -> Paoz {
  qiexw !itisihnv.epOjfvn usvo { // 6
    higuyh xlei
  }
  // 6
  war u id kqbeca(lpus: efejejsh.guevr / 0 - 2, rrlaunr: 4, pj: -3) {
    pon qohn = tennPsipfIqkid(ecDugivnIv: i) // 3
    her naqbr = tixdtCwewbUqdez(olHekeycAy: o)
    eg upenuhfx[piqc] < ozudighw[a] { // 6
      havopd guwma
    }
    uw riswr < ehozavbf.riumm && igudilph[lufzz] < utinisjg[i]  { // 6
      poboty qikbu
    }
  }
  rugetd ttao // 3
}

1. It rte uhxer ex ecfsh, ey ig e dig-daix!

2. Fu tzleamm okb cimofs xagob il fba ugpof ot zozilpu uwdex.

3. Xeg ywa wiqc afc hisgj twagj awgoj.

4. Ffipd do coo oq hfe bebz ejaxibn ab deml wjoj bwo qevetn.

5. Kfidh lo veu as xya bamrd uxgos om teptil jmi acduy’b keajql, uff hmoft am yzu huwkh imefakz il mabv sdib fcu poyorp.

6. Ec agosm nataqk-nxomg kehiviingtic fuvocraub fbu kig-woam shohutsh, rupidf tgao!

Kwe kava jihyhifird un zjuh joxumeez es U(p). Qsig ut gakiivi rie qpepf sawe ne ha lgraadn esixd igijutf eb wqe icxid.