python (65.1k questions)

javascript (44.2k questions)

reactjs (22.7k questions)

java (20.8k questions)

c# (17.4k questions)

html (16.3k questions)

r (13.7k questions)

android (12.9k questions)

Questions - heap

Find the Kth smallest element in a matrix of sorted rows

This is an interview question. Find the Kth smallest element in a matrix of sorted rows, but NOT sorted columns and no relations between the rows. (the first row and nth row have no relation between t...
test-img

s_jack_frost

java

algorithm

heap

Votes: 0

Answers: 6

Latest Answer

Assume the following case [[1,3,4,...10], [1,3,4,...10], [1,2,4,...10]] For k = 4, ans = 2 Since each row has the same starting/ending element and there's no relation between any two rows, it's hard ...
test-img

Abhinav Mathur

Performance improvement for Dijkstra algorithm using heaps in python?

Below is my implementation for Dijkstra's algorithm using heaps (for undirected graphs). This works just fine for reasonably sized graphs however I am not satisfied by my code for recalculating greedy...
test-img

tim_76

python

dijkstra

heap

Votes: 0

Answers: 1

Latest Answer

There are several alternative implementations of Dijkstra's algorithm, but none of them need to iterate through the heap, nor remove arbitrary nodes from it, nor re-heapify it repeatedly. All those ac...
test-img

trincot

Why does the Python heapq _siftup(...) call _siftdown(...) at the end?

The code for_siftup at github - python/cpython/Lib/heapq.py has a final call to _siftdown: def _siftup(heap, pos): endpos = len(heap) startpos = pos newitem = heap[pos] # Bubble up th...
test-img

aksg87

python

heap

heapq

Votes: 0

Answers: 1

Latest Answer

This is the consequence of a particular choice the authors made in the algorithm. More common is an algorithm where this final _siftdown() is not necessary, but then the loop must stop when newitem &l...
test-img

trincot

Inserting a node in a min-heap with a null value at the end

I got a sorted min-heap array: 2,3,4,5,NULL I'd like to insert the value 1 in it, how would the first step be dealt with? 2 2 / \ / \ 3 4 ...
test-img

student

arrays

binary

binary-tree

heap

min-heap

Votes: 0

Answers: 1

Latest Answer

A heap of integers does not have NULL values. I suppose the NULL is an indication of the capacity of the heap, meaning it can only have one more value before being full. Would be this the same if the...
test-img

trincot

Posts

Questions

Blogs

Jobs