Heap: Given a n x n matrix where each of the rows and columns are sorted in ascending order, findthe kth smallest element in the matrix in Python

[akgmage]

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:
Input:
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
Output: 13
Note:
You may assume k is always valid, 1 ≤ k ≤ n^2. You may also assume that 1 <= n <= 1000.