cách xác định xem phần tử lớn nhất thứ k của heap có lớn hơn x

Question

Xem xét một đống nhị phân chứa n số (gốc lưu trữ số lớn nhất). Bạn được cung cấp số nguyên dương k < n và một số x. Bạn phải xác định liệu yếu tố lớn nhất thứ k của heap có lớn hơn x hay không. Thuật toán của bạn phải mất thời gian O (k). Bạn có thể sử dụng bộ nhớ bổ sung O (k)

Answer 1

Dfs đơn giản có thể làm điều đó, chúng tôi có bộ đếm được đặt bằng không. Bắt đầu từ gốc và trong mỗi lần lặp kiểm tra giá trị nút nếu lớn hơn x, sau đó tăng thuật toán truy cập và chạy cho các nút con. Khi bộ đếm lớn hơn hoặc bằng k thuật toán sẽ được hoàn thành, cũng nếu không có nút nào để kiểm tra, thuật toán sẽ trả về false. Mã đơn giản. Thời gian chạy là O (k) bởi vì nhiều nhất bạn sẽ kiểm tra nút k và mỗi lần lặp là O (1).

Mã giả trông giống như sau.

void CheckNode(Node node,int k, int x, ref int counter) 
    { 
     if (node.value > x) 
     { 
      counter++; 
      if (counter >= k) 
       return; 

      CheckNode(node.Left, k, x, ref counter); 
      CheckNode(node.Right,k, x, ref counter); 
     } 
    } 

sử dụng nó:

 counter = 0; 
     CheckNode(root,index,val,counter); 
     if (counter >= index) 
      return true; 
     return false; 

nếu node.value < x sau đó tất cả trẻ em giá trị nhỏ hơn x và không có cần phải kiểm tra.

Như @Eric Mickelsen đã đề cập trong phần bình luận trường hợp xấu nhất thời gian chạy chính xác là 2k-1 (k> 0) như sau.

Số lượng nút được truy cập có giá trị lớn hơn x sẽ tối đa là k. Mỗi nút được truy cập có giá trị nhỏ hơn x phải là con của một nút được truy cập có giá trị lớn hơn x. Tuy nhiên, vì mọi nút được truy cập ngoại trừ gốc phải có cha hoặc mẹ có giá trị lớn hơn x, số lượng nút có giá trị nhỏ hơn x được truy cập phải tối đa là ((k-1) * 2) - (k-1)) = k-1, vì k-1 của (k-1) * 2 trẻ có giá trị lớn hơn x. Điều này có nghĩa là chúng tôi truy cập các nút k lớn hơn x và k-1 nhỏ hơn x, là 2k-1.

Answer 2

public class KSmallest2 { 

private MinPQ<Integer> minHeap; 
private int x; 
private int k; 
private int count = 0; 

public KSmallest2(String filename, int x, int k) { 
    this.x = x; 
    this.k = k; 
    minHeap = new MinPQ<>(); 
    try { 
     Scanner in = new Scanner(new File(filename)); 
     while (in.hasNext()) { 
      minHeap.insert(in.nextInt()); 
     } 
    } catch (FileNotFoundException e) { 
     e.printStackTrace(); 
    } 
} 

public boolean check(int index) { 

    if (index > minHeap.size()) { 
     return false; 
    } 

    if (minHeap.getByIndex(index) < x) { 
     count++; 
     if (count >= k) { 
      return true; 
     } 

     return check(2 * index) || 
       check(2 * index + 1); 
    } 

    return false; 
} 



public static void main(String[] args) { 
    KSmallest2 ks = new KSmallest2("src/main/resources/minheap.txt", 18, 5); 
    System.out.println(ks.minHeap); 

    System.out.println(ks.check(1)); 
} 

}