Het maken van een heap kost O(n)tijd, terwijl het invoegen in een heap (of prioriteitswachtrij) O(log(n))tijd kost.
Als we n invoer nemen en deze in de prioriteitswachtrij plaatsen, wat zou dan de tijdscomplexiteit van de bewerking zijn?O(n) of O(n*log(n)).
Ook zou hetzelfde resultaat gelden in het geval van het legen van de hele heap (d.w.z. n verwijderingen), toch?
Antwoord 1, autoriteit 100%
Als je een array met de grootte nhebt en je wilt een hoop van alle items tegelijk bouwen, dan kan het algoritme van Floyd dit doen met O(n) complexiteit. Zie Een hoop bouwen. Dit komt overeen met de std::priority_queue-constructorsdie een containerparameter accepteren.
Als je een lege prioriteitswachtrij hebt waaraan je nitems één voor één wilt toevoegen, dan is de complexiteit O(n * log(n)).
Dus als je alle items hebt die in je wachtrij komen voordat je deze gaat bouwen, dan is de eerste methode efficiënter. U gebruikt de tweede methode – items afzonderlijk toevoegen – wanneer u een wachtrij moet onderhouden: elementen toevoegen en verwijderen gedurende een bepaalde periode.
Het verwijderen van nitems uit de prioriteitswachtrij is ook O(n * log(n)).
Documentatie voor std::priority_queueomvat runtime-complexiteit van alle bewerkingen.