I have to get k smallest elements from the list of N Numbers. My approach is to make a min heap and then extract first k elements.
How i do that is to insert n elements one by one into the heap and use heapify up method to make it min heap. Then extract k elements one by one and use heapify down to have the min heap properties sustained.
this is the Golang Code:
type Minheap struct {
nums []int
}
func (h *Minheap) insert(key int) {
h.nums = append(h.nums, key)
h.minHeapifyUp(len(h.nums) - 1)
}
func (h *Minheap) minHeapifyUp(index int) {
for h.nums[getparentIndex(index)] > h.nums[index] {
h.swap(getparentIndex(index), index)
index = getparentIndex(index)
}
}
func (h *Minheap) swap(i1, i2 int) {
h.nums[i1], h.nums[i2] = h.nums[i2], h.nums[i1]
}
func getparentIndex(index int) int {
return (index - 1) / 2
}Question 1: Is this a good approach to it?
Question 2 : Can we make min heap of just K elements. Lets say N = 7 and k = 3. Initially we insert 3 elements and when we are about to insert 4th element (index = 3) can we not replace it with some other element's place so the heap will still contain 3 elements only?