algorithm - Deleting a node A[i] from a Max-Heap -

-

clrs exercise: 6.5-8

the operation heap-delete(a,i) deletes item in node i heap a. give implementation of heap-delete runs in o(lg n) time n-element max-heap.

enter image description here

i wonder if algorithm wrong input a[10]={84,22,19,21,3,10,6,5,20}(index starts 1) , a[6]=10 being deleted. replacing last node a[6] result in violating heap property, overlooking parent value.

i wrote algorithm , wanted know if works right or going wrong ?

heap-delete(a,i)   a[i]=a[a.heapsize]   a.heapsize-=1   while i>1 , a[parent(i)]<a[i]     swap a[i] a[parent(i)]     i=parent(i);

when deleting node max heap, first thing need swap target element last element, delete last element.

now, we're faced problem of fixing max heap since moved element around. let's refer element moved x.

there 3 cases:

  • x greater parent
  • x less parent
  • x equal parent

if x equal parent, that's easy - nothing.

if x less parent, need max-heapify (which i'm assuming understand how works comments), because need fix mistakes below x.

if x greater parent, run issue you've brought up. handling isn't tricky - need compare x parent, , if x greater parent, swap them. continue process until x no longer greater parent or reach root (when x has no parents).

with being said, pseudocode you've posted looks right me. nice work :)


Comments

Post a Comment

Popular posts from this blog

javascript - Slick Slider width recalculation -

-
i'm trying add slide in panel on slick container css. carousel works except new width not being calculated when space has been added. recalibrate once advance next slide i'd happen each time panel opened or closed. i've tried adding both margin , padding, neither makes difference. ideas? https://jsfiddle.net/mhigley/dpf7mlpl/ html: <button type="button" id="button"><i class="fa fa-arrow-right"></i></button> <aside> <h2>slide in panel</h2> <ol> <li>list item</li> <li>list item</li> <li>list item</li> <li>list item</li> <li>list item</li> </ol> </aside> <main role="main"> <div class="sections"> <section> <article> <h2>first slide</h2> <p>lorem ipsum d...
Read more

jsf - PrimeFaces Datatable - What is f:facet actually doing? -

-
looking through primefaces code in app noticed following line: <f:facet name="header">#{trainsearch.traincount} trains</f:facet> it looks overriding header, makes sense, can explain me in little more detail? what happening line of code? complete code listed below: <p:datatable id = "results" value = "#{trainsearch.trains}" var = "train" rendered="#{not empty trainsearch.trains}" styleclass = "train-search-table horizontal-border"> <f:facet name="header">#{trainsearch.traincount} trains</f:facet> <p:column headertext = "train id"> <p:panelgrid columns="1" styleclass = "train-id-grid" layout = "grid"> <h:outputtext styleclass = "train-id-label" value="#{train.traini}"/> <h:outputtex...
Read more

angular2 services - Angular 2 RC 4 Http post not firing -

-
i trying fire post request app , it's not working, tried multiple ways. don't see request being fired under network tab in chrome. not sure problem is, appreciated. import { injectable } '@angular/core'; import { http, headers } '@angular/http'; @injectable() export class userservice{ private _url="users"; constructor(private _http: http){ } checkifusernameexists(username){ return this._http.get(this._url+"/"+username) .map(response => response.json()) } createuser(user){ let headers = new headers(); headers.append('content-type', 'application/json') console.log(json.stringify(user)); return this._http.post(this._url, json.stringify(user),{headers: headers}) .map(response => response.json()) } } first need capture error , solve error: this._http.post(this._url, json.stringify(user),{headers: headers}) .subscribe( ...
Read more