Commit502d663

committed

Add max heap approach for No.215

Signed-off-by: begeekmyfriend <begeekmyfriend@gmail.com>

1 parentd4f6d7e commit502d663Copy full SHA for 502d663

File tree

1 file changed

+44

-0

lines changed

0215_kth_largest_element_in_an_array
- kth_elem.c

1 file changed

+44

-0

lines changed

`‎0215_kth_largest_element_in_an_array/kth_elem.c‎`

Lines changed: 44 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -1,13 +1,43 @@`
`1`	`1`	`#include<stdio.h>`
`2`	`2`	`#include<stdlib.h>`
`3`	`3`
	`4`	`+`
`4`	`5`	`staticinlinevoidswap(inta,intb)`
`5`	`6`	`{`
`6`	`7`	`intt=*a;`
`7`	`8`	`a=b;`
`8`	`9`	`*b=t;`
`9`	`10`	`}`
`10`	`11`
	`12`	`+staticvoidmax_heapify(int*nums,intsize,intparent)`
	`13`	`+{`
	`14`	`+inti=parent;/* parent is the root */`
	`15`	`+intl=parent*2+1;`
	`16`	`+intr=parent*2+2;`
	`17`	`+`
	`18`	`+if (l<size&&nums[l]>nums[i]) {`
	`19`	`+i=l;`
	`20`	`+ }`
	`21`	`+`
	`22`	`+if (r<size&&nums[r]>nums[i]) {`
	`23`	`+i=r;`
	`24`	`+ }`
	`25`	`+`
	`26`	`+/* percolate up */`
	`27`	`+if (i!=parent) {`
	`28`	`+swap(&nums[i],&nums[parent]);`
	`29`	`+max_heapify(nums,size,i);`
	`30`	`+ }`
	`31`	`+}`
	`32`	`+`
	`33`	`+staticvoidbuild_max_heap(int*nums,intsize)`
	`34`	`+{`
	`35`	`+inti;`
	`36`	`+for (i=size /2;i >=0;i--) {`
	`37`	`+max_heapify(nums,size,i);`
	`38`	`+ }`
	`39`	`+}`
	`40`	`+`
`11`	`41`	`staticintquick_select(int*nums,intlo,inthi,intk)`
`12`	`42`	`{`
`13`	`43`	`if (lo >=hi) {`
`@@ -40,8 +70,22 @@ static int quick_select(int *nums, int lo, int hi, int k)`
`40`	`70`
`41`	`71`	`intfindKthLargest(int*nums,intnumsSize,intk)`
`42`	`72`	`{`
	`73`	`+#if0`
`43`	`74`	`inti=quick_select(nums,0,numsSize-1,k);`
`44`	`75`	`returnnums[i];`
	`76`	`+#else`
	`77`	`+inti;`
	`78`	`+`
	`79`	`+build_max_heap(nums,numsSize);`
	`80`	`+`
	`81`	`+/* nums[0] is the largest element and the last is the least */`
	`82`	`+for (i=numsSize-1;i >=numsSize-k+1;i--) {`
	`83`	`+swap(&nums[0],&nums[i]);`
	`84`	`+max_heapify(nums,numsSize,0);`
	`85`	`+ }`
	`86`	`+`
	`87`	`+returnnums[0];`
	`88`	`+#endif`
`45`	`89`	`}`
`46`	`90`
`47`	`91`

0 commit comments

Comments

(0)

Movatterモバイル変換

Navigation Menu

Search code, repositories, users, issues, pull requests...

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Commit502d663

File tree

1 file changed

1 file changed

`‎0215_kth_largest_element_in_an_array/kth_elem.c‎`

0 commit comments