Phần tử thứ K trong cây heap

Question

Tôi có một đống (được thực hiện như một cây nhị phân: mỗi nút có hai con trỏ tới con và một con trỏ đến con trỏ).

Làm cách nào để tìm phần tử thứ k (theo thứ tự BFS), với số phần tử trong đó? Tôi nghĩ rằng nó có thể được thực hiện trong thời gian O (logn) ..

Answer 1

(Tôi giả định bởi "yếu tố thứ k (theo thứ tự BFS)" mà bạn có nghĩa là yếu tố thứ k từ góc nhìn từ trên xuống dưới , quét từ trái sang phải của đầu vào.)

Vì bạn biết rằng một đống nhị phân là một cây nhị phân hoàn chỉnh (ngoại trừ ở mức cuối cùng), bạn biết rằng hình dạng của cây là một cây nhị phân hoàn hảo của một số chiều cao (có chứa 2 ^k nút cho một số k) với một số nút được điền từ trái sang phải. Một tài sản thực sự tiện lợi của những cây xảy ra khi bạn viết ra những con số của các nút trong một bức tranh, một chỉ mục các giá trị:

     1 
      2    3 
     4  5  6  7 
     8 9 10 11 12 13 14 15 

Chú ý rằng mỗi lớp bắt đầu với một nút đó là một sức mạnh của hai. Vì vậy, chúng ta hãy giả sử, giả thuyết, mà bạn muốn tìm kiếm các số 13. Sức mạnh lớn nhất của hai không lớn hơn 13 là 8, vì vậy chúng tôi biết rằng 13 phải xuất hiện ở hàng

8 9 10 11 12 13 14 15 

Bây giờ chúng ta có thể sử dụng này kiến thức để đảo ngược-kỹ sư đường dẫn từ 13 trở lại đến gốc của cây. Ví dụ, chúng ta biết rằng 13 nằm trong nửa sau của các con số trong hàng này, có nghĩa là 13 thuộc về cây con phải của gốc (nếu nó thuộc về cây con trái, thì chúng ta sẽ ở trong cây con chứa 8, 9, 10 và 11.) Điều này có nghĩa là chúng ta có thể đi ngay từ gốc và ném ra một nửa số để có được

12 13 14 15 

Hiện tại chúng tôi đang ở nút 3 trong cây. Vậy chúng ta đi sang trái hay phải? Vâng, 13 là trong nửa đầu của những con số này, vì vậy chúng tôi biết vào thời điểm này mà chúng ta cần phải đi vào bên trái cây con của nút 3. Điều này đưa chúng ta đến nút 6, và bây giờ chúng tôi còn lại với nửa đầu của số điện thoại:

12 13 

13 nằm ở nửa bên phải của các nút này, vì vậy chúng tôi sẽ xuống bên phải, đưa chúng tôi đến nút 13. Và thì đấy! Đã ở đó!

Vậy quy trình này hoạt động như thế nào? Vâng, có một mẹo thực sự, rất dễ thương mà chúng ta có thể sử dụng. Hãy viết ra cùng một cây, chúng tôi đã nêu trên, nhưng trong hệ nhị phân:

     0001 
      0010     0011 
     0100  0101  0110  0111 
    1000 1001 1010 1011 1100 1101 1110 1111 
           ^^^^ 

tôi đã chỉ ra vị trí của nút 13. Thuật toán của chúng tôi làm việc theo cách sau:

1. Tìm lớp chứa nút.
2. Trong khi không ở nút được đề cập:
   1. Nếu nút nằm trong nửa đầu của lớp, hãy di chuyển sang trái và vứt nửa bên phải của phạm vi.
   2. Nếu nút nằm trong nửa thứ hai của lớp đó, hãy di chuyển sang phải và vứt nửa trái của phạm vi.

Hãy suy nghĩ về điều này có nghĩa trong hệ nhị phân.Tìm lớp chứa nút là tương đương với việc tìm bit quan trọng nhất được đặt trong số. Trong 13, trong đó có đại diện nhị phân 1101, MSB là 8 bit. Điều này có nghĩa là chúng ta đang ở trong lớp bắt đầu với tám.

Vậy làm cách nào để chúng tôi xác định xem chúng tôi có ở cây con trái hay cây con phải không? Vâng, để làm điều đó, chúng ta sẽ cần phải xem chúng ta đang ở nửa đầu của lớp này hay nửa thứ hai. Và bây giờ cho một thủ thuật dễ thương - nhìn vào bit tiếp theo sau MSB. Nếu bit này được đặt thành 0, chúng tôi đang ở nửa đầu của phạm vi và nếu không chúng tôi đang ở nửa sau của phạm vi. Vì vậy, chúng ta có thể xác định được một nửa phạm vi mà chúng ta đang ở bằng cách chỉ nhìn vào bit tiếp theo của số! Điều này có nghĩa là chúng ta có thể xác định cây con nào đi vào bằng cách nhìn vào bit tiếp theo của số.

Khi chúng tôi đã thực hiện điều đó, chúng tôi chỉ có thể lặp lại quy trình này. Chúng ta làm gì ở cấp độ tiếp theo? Vâng, nếu bit tiếp theo là số không, chúng ta đi bên trái, và nếu bit tiếp theo là một, chúng ta đi đúng. Hãy nhìn vào những gì này có nghĩa là 13:

1101 
    ^^^ 
    ||| 
    ||+--- Go right at the third node. 
    || 
    |+---- Go left at the second node. 
    | 
    +----- Go right at the first node. 

Nói cách khác, chúng ta có thể giải thích rõ ràng các đường đi từ thư mục gốc của cây để nút của chúng tôi trong câu hỏi chỉ cần nhìn vào các bit của số sau khi MSB !

Tính năng này có hoạt động không! Bạn đặt cược! Hãy thử số 7. Điều này có đại diện nhị phân 0111. MSB là ở vị trí của 4. Sử dụng thuật toán của chúng tôi, chúng tôi sẽ làm điều này:

0111 
    ^^ 
    || 
    |+--- Go right at the second node. 
    | 
    +---- Go right at the first node. 

Nhìn vào hình ảnh ban đầu của chúng tôi, đây là con đường phù hợp để thực hiện!

Dưới đây là một số thô C/C++ giả cho thuật toán này:

Node* NthNode(Node* root, int n) { 
    /* Find the largest power of two no greater than n. */ 
    int bitIndex = 0; 
    while (true) { 
     /* See if the next power of two is greater than n. */ 
     if (1 << (bitIndex + 1) > n) break; 
     bitIndex++; 
    } 

    /* Back off the bit index by one. We're going to use this to find the 
    * path down. 
    */ 
    bitIndex--; 

    /* Read off the directions to take from the bits of n. */ 
    for (; bitIndex >= 0; bitIndex--) { 
     int mask = (1 << bitIndex); 
     if (n & mask) 
      root = root->right; 
     else 
      root = root->left; 
    } 
    return root; 
} 

tôi đã không kiểm tra mã này! Để diễn giải Don Knuth, tôi đã chỉ ra rằng khái niệm nó làm điều đúng. Tôi có thể có một lỗi off-by-one ở đây.

Vậy mã này nhanh như thế nào? Vâng, vòng lặp đầu tiên chạy cho đến khi nó tìm thấy sức mạnh đầu tiên của hai lớn hơn n, mất thời gian O (log n). Phần tiếp theo của vòng lặp đếm ngược thông qua các bit của n một lần, làm O (1) làm việc ở mỗi bước. Do đó, tổng số thuật toán tổng cộng là O (log n) time.

Hy vọng điều này sẽ hữu ích!