A Kup je popolna binarna drevesna podatkovna struktura, ki izpolnjuje lastnost kopice: za vsako vozlišče je vrednost njegovih otrok manjša ali enaka njegovi lastni vrednosti. Kope se običajno uporabljajo za izvajanje prednostnih čakalnih vrst, kjer je najmanjši (ali največji) element vedno v korenu drevesa.

matriko v jeziku c

Struktura podatkov kopice

Kazalo

• Vrste kopic
• Operacije kopice
• Kaj je Heap Data Structure?

  A kup je binarna drevesna podatkovna struktura, ki izpolnjuje lastnost kopice: vrednost vsakega vozlišča je večja ali enaka vrednosti njegovih otrok. Ta lastnost zagotavlja, da korensko vozlišče vsebuje maksimum oz najmanj vrednost (odvisno od vrste kopice), vrednosti pa se zmanjšujejo ali povečujejo, ko se premikate po drevesu navzdol.

  Vrste kopic

  Obstajata dve glavni vrsti kupov:

  
  
  
  
  • Največji kup: Korensko vozlišče vsebuje največjo vrednost, vrednosti pa se zmanjšujejo, ko se premikate po drevesu navzdol.
  • Najmanjša kopica: Korensko vozlišče vsebuje najmanjšo vrednost, vrednosti pa se povečujejo, ko se premikate po drevesu navzdol.

  Operacije kopice

  Pogoste operacije kopice so:

  • Vstavi : doda nov element v kopico, pri tem pa ohrani lastnost kopice.
  • Največ/najmanj ekstrahiranja: Odstrani največji ali najmanjši element iz kopice in ga vrne.
  • Heapify : Pretvori poljubno binarno drevo v kopico.

  Kope se običajno uporabljajo za izvajanje prednostnih čakalnih vrst, kjer se elementi pridobijo na podlagi njihove prioritete (največja ali najmanjša vrednost).

• Heapsort je algoritem za razvrščanje, ki uporablja kopico za razvrščanje matrike v naraščajočem ali padajočem vrstnem redu.
• Kope se uporabljajo v algoritmih grafov, kot je Dijkstrajev algoritem in Primov algoritem za iskanje najkrajših poti in minimalnih vpetih dreves.

Binarna kopica

Aplikacije, prednosti in slabosti Heap

Čas Kompleksnost gradnje kupa

Primerjava med kupom in drevesom

Ali je pri gradnji Heap struktura Heap edinstvena?

Fibonaccijeva kopica

Levičarski kup

K-ary Heap

Razvrščanje kopice

Preverite, ali je dano binarno drevo kopica

Kako preveriti, ali podana matrika predstavlja binarno kopico?

Iterativno razvrščanje kopice

K-ti največji element v nizu

K’th najmanjši/največji element v nerazvrščenem nizu | Komplet 1

Višina celotnega binarnega drevesa (ali kopice) z N vozlišči

Kopica Razvrsti za padajoči vrstni red z uporabo najmanjše kopice

Natisnite vsa vozlišča, manjša od vrednosti x v minimalni kopici.

Drevo turnirjev (drevo zmagovalcev) in dvojiška kopica

Povežite n vrvi z minimalnimi stroški

Največje število različnih elementov po odstranitvi k elementov

K največje vsote kombinacij iz dveh nizov

Mediana toka tekočih celih števil z uporabo STL

Mediana v toku celih števil (tekoča cela števila)

K-ti največji element v toku

Največji trojni izdelek v toku

Poiščite k števil z največ pojavitvami v dani matriki

Pretvori najmanjšo kopico v največjo kopico

Glede na prečkanje vrstnega reda ravni binarnega drevesa preverite, ali je drevo minimalna kopica

Spoji k razvrščenih nizov | Komplet 1

Razvrstite številke, shranjene na različnih napravah

Najmanjša motnja zaporedja

Največja motnja zaporedja

Največja razlika med dvema podmnožicama m elementov

Pretvorite BST v Min Heap

Združite dva binarna Max Heapa

K-ti največji sosednji podniz vsote

Najmanjši zmnožek k celih števil v nizu pozitivnih celih števil

Preuredite znake v nizu tako, da nobena dva sosednja nista enaka

Vsota vseh elementov med k1 in k2 najmanjšim elementom

Najmanjša vsota dveh števil, sestavljena iz števk matrike

Hitre povezave:

• Vadite naloge na kupu
• Priporočeno:
  • Naučite se podatkovne strukture in algoritmov | Vadnica DSA