6:50: the elements already exist in the array, so what I think he does is just apply the down heapify (reheapification downward) on the elements that are considered as parents nodes which are n//2 elements, and start from down, upward from n//2-1 to 0 heapify each parent with its children to build the heap,. so the number of steps will decrease by a factor of 2 so I think building the heap would still be O(N*logN) but of course, the running time will decrease.
level (0): The count of elements = 2^0 = 1, The operation of down heapify of each node = log2(n)-0 level (1): The count of elements 2^1 = 2, The operation of down heapify of each node = log2(n)-1 level (2): The count of elements 2^2 = 4, The operation of down heapify of each node = log2(n)-2 .............. ............. level(log2(n)): The count of elements = 2^log2(n), The operation of down heapify = log2(n)-log2(n) = 0 Then the total time is 1*(log2(n)-0) + 2*(log2(n)-1) + 3*(log2(n)-2) + .... + 2^log2(n)*0 if you do analysis the time complexity will be O(n)
![#029 [Data Structures] - Heap Sort Algorithm(Heapify,Build heap,Max-Min heap) With Implementation](/img/n.gif)
6:50: the elements already exist in the array, so what I think he does is just apply the down heapify (reheapification downward) on the elements that are considered as parents nodes which are n//2 elements, and start from down, upward from n//2-1 to 0 heapify each parent with its children to build the heap,.
so the number of steps will decrease by a factor of 2
so I think building the heap would still be O(N*logN) but of course, the running time will decrease.
level (0): The count of elements = 2^0 = 1, The operation of down heapify of each node = log2(n)-0
level (1): The count of elements 2^1 = 2, The operation of down heapify of each node = log2(n)-1
level (2): The count of elements 2^2 = 4, The operation of down heapify of each node = log2(n)-2
..............
.............
level(log2(n)): The count of elements = 2^log2(n), The operation of down heapify = log2(n)-log2(n) = 0
Then the total time is 1*(log2(n)-0) + 2*(log2(n)-1) + 3*(log2(n)-2) + .... + 2^log2(n)*0
if you do analysis the time complexity will be O(n)
جزاك الله خيرا كثيرا
عظمه اقسم بالله
YOU’RE THE BEST
Check out the Udemy DS course: more easier and direct
شرح مفهوم.شكراا