#### Concepts Used

Heap

#### Difficulty Level

Hard

#### Problem Statement :

Given the heights of

`N`

buildings and an integer`k`

find the height of`kth`

highest building.

**See original problem statement here**

#### Solution Approach :

#### Introduction :

Idea is to create a

max-heapof heights of buildings, in order to get`kth`

highest height we need go remove first`k-1`

largest height.

#### Method 1 :

Sort the array containing heights of the buildings in decreasing order using any sorting algorithm in data structures and algorithms.. Now print the

`kth`

value in the array which is the`kth`

highest height.

#### Method 2 :

Geneate a

max-heapfrom the heights of the buildings.In a

max-heap, the root always stores the larger value as compared to itsleft&rightsubtree, this condition needs to be true for every node. We need to insert each item one by one such that parent is always larger than the item itself. If parent is smaller, then swap the current item with its parent.After generating

max-heapnowextractfirst`k-1`

heights from the heap. Among the remaining heights, the first element of the heap (`heap[0]`

) is the`kth`

highest element.

extract(): Removes the maximum element fromMax-Heap. Time Complexity of this Operation is O(Logn) as this operation needs to maintain the heap property (by callingheapify()) after removing root.

heapify(): Maintains the heap property for each node. If any node does not follow heap property it swaps the node with the node which is smaller ,or greater (in case ofmax-heap), than the node.

#### Algorithms :

**Insert()** :

- Insert the item at the last index, and increment the size by 1.
- Then, check if the inserted item is smaller than its parent,
- If yes, then swap the inserted item with its parent.
- If no, then do nothing.
- Now, go to step
`2`

and repeat untill we reach root (first element).

**Extract()** :

- Store the value of the first node of our heap (
`temp = heap[0]`

).- Replace the root node with the farthest right node (last element).
- Decrease the size by
`1`

.`(heap[0] = heap[size-1])`

- Perform
heapifystarting from the new root.- Return the stored value (
`temp`

).

**Heapify ()** :

- if the heap property holds true then you are done.
- else if
- the replacement node value < its parent nodes value

then swap them, and repeat step 3.- else
- swap the replacement node with the largest child node, and

repeat step 3.

#### Example:

#### Solutions:

[TABS_R id=1602]

[forminator_quiz id=”1608″]