2. queue.py

973. K Closest Points to Origin
https://leetcode.com/problems/k-closest-points-to-origin/submissions/
class Solution(object):
    def kClosest(self, points, K):
        """
        :type points: List[List[int]]
        :type K: int
        :rtype: List[List[int]]
        """
        #------------------priority queue---------------
        # O(n) n= len(points)
        q= []
        
        for point in points:
            x, y= point[0], point[1]
            distance= x**2 + y**2
            q.append( [distance, point] )
        q.sort()
        
        return [ point for _, point in q[:K] ]

maza.java

class mazeII{
    int[][] dir=new int[][] {{-1,0},{0,1},{1,0},{0,-1}};

    public int shortestDistance(int[][] maze, int[] st, int[] dst) {
        int m=maze.length, n=maze[0].length;
        
        int[][] distance=new int[m][n]; // record length
        for(int[] d: distance) 
        	Arrays.fill(d, Integer.MAX_VALUE);
        
        PriorityQueue<int[]> minHeap=new PriorityQueue<>((a, b)-> a[2]- b[2]); // using priority queue
        minHeap.add(new int[]{st[0], st[1], 0} );//x, y, distance
        
        while (!minHeap.isEmpty()) {
            int[] cell= minHeap.remove();
            
            if (distance[cell[0]][cell[1]]<= cell[2]) continue; // if we have already found a route shorter
            distance[cell[0]][cell[1]]= cell[2];
            
            for (int k=0;k<4;k++) {
                int i=cell[0], j=cell[1], dist=cell[2];
                i+=dir[k][0];
                j+=dir[k][1];
                
                if (0<=i && i<m && 0<=j && j<n && maze[i][j]==0) {
                    minHeap.add(new int[] {i, j, dist+1});
                }
            }
        }
        
        
        for( int[] row: distance) {
        	System.out.println( Arrays.toString(row));
        }
        
        return distance[dst[0]][dst[1]]==Integer.MAX_VALUE?-1:distance[dst[0]][dst[1]];
    }
}


class mazeIII{
    int[][] dir=new int[][] {{0, 1},{0, -1},{1, 0},{-1, 0}};
    String[] ds=new String[] {"R","L","D","U"};

	class Cell implements Comparable<Cell> {
        int x,y,dist;
        String s;
        
        public Cell(int x, int y, int dist, String s) {
        	this.x= x;
        	this.y= y;
        	this.dist= dist;
        	this.s= s;
        }
        
        public int compareTo(Cell c) {
        	return dist==c.dist ? s.compareTo(c.s) : this.dist-c.dist;
        }
    }
	
    public void findShortestWay(int[][] maze, int[] st, int[] dst) {
        int m=maze.length, n=maze[0].length;
        
        int[][] distance=new int[m][n]; // record length
        for(int[] d: distance) 
        	Arrays.fill(d, Integer.MAX_VALUE);
        
        PriorityQueue<Cell> minQueue=new PriorityQueue<>(); // using priority queue
        
        minQueue.add( new Cell( st[0], st[1], 0, "") );
        
        while (!minQueue.isEmpty()) {
            Cell c=minQueue.remove();
            
            if ( distance[c.x][c.y] <= c.dist) continue; // if we have already found a route shorter
            distance[c.x][c.y] = c.dist;
            if( c.x==dst[0] && c.y==dst[1]) {
            	System.out.println( c.s );
            }
           
            for (int k=0;k<4;k++) {
                int i=c.x, j=c.y, dist=c.dist;
                i+=dir[k][0];
                j+=dir[k][1];
                if (0<=i && i<m && 0<=j && j<n && maze[i][j]==0 ) {
                    minQueue.add(new Cell(i, j, dist+1, c.s+ds[k]));
                }
            }
        }
        
        for( int[] d: distance) {
        	System.out.println( Arrays.toString(d));
        }
        
    }
}