Median Aliran Integer menggunakan Heap di Java

1. Ikhtisar

Dalam tutorial ini, kita akan belajar cara menghitung median aliran bilangan bulat.

Kami akan melanjutkan dengan menyatakan masalah dengan contoh, kemudian menganalisis masalah, dan akhirnya menerapkan beberapa solusi di Java.

2. Pernyataan Masalah

Median adalah nilai tengah dari kumpulan data yang diurutkan. Untuk satu set bilangan bulat, ada banyak elemen yang kurang dari median yang lebih besar.

Dalam satu set terurut:

  • bilangan bulat ganjil, elemen tengahnya adalah median - dalam himpunan berurutan {5, 7, 10} , mediannya adalah 7
  • bilangan bulat genap, tidak ada elemen tengah; median dihitung sebagai rata-rata dari dua elemen tengah - dalam himpunan berurutan {5, 7, 8, 10} , mediannya adalah (7 + 8) / 2 = 7,5

Sekarang, mari kita asumsikan bahwa alih-alih himpunan terbatas, kita membaca bilangan bulat dari aliran data. Kita dapat mendefinisikan median aliran bilangan bulat sebagai median himpunan bilangan bulat yang telah dibaca sejauh ini .

Mari meresmikan pernyataan masalah. Diberikan masukan dari aliran bilangan bulat, kita harus merancang kelas yang melakukan dua tugas berikut untuk setiap bilangan bulat yang kita baca:

  1. Tambahkan bilangan bulat ke kumpulan bilangan bulat
  2. Temukan median dari bilangan bulat yang telah dibaca sejauh ini

Sebagai contoh:

add 5 // sorted-set = { 5 }, size = 1 get median -> 5 add 7 // sorted-set = { 5, 7 }, size = 2 get median -> (5 + 7) / 2 = 6 add 10 // sorted-set = { 5, 7, 10 }, size = 3 get median -> 7 add 8 // sorted-set = { 5, 7, 8, 10 }, size = 4 get median -> (7 + 8) / 2 = 7.5 .. 

Meskipun alirannya tidak terbatas, kita dapat berasumsi bahwa kita dapat menyimpan semua elemen aliran dalam memori sekaligus.

Kami dapat mewakili tugas kami sebagai operasi berikut dalam kode:

void add(int num); double getMedian(); 

3. Pendekatan Naif

3.1. Daftar yang Diurutkan

Mari kita mulai dengan ide sederhana - kita dapat menghitung median dari daftar bilangan bulat yang diurutkan dengan mengakses elemen tengah atau dua elemen tengah dari daftar , dengan indeks. Kompleksitas waktu operasi getMedian adalah O (1) .

Saat menambahkan bilangan bulat baru, kita harus menentukan posisinya yang benar dalam daftar agar daftar tetap diurutkan. Operasi ini dapat dilakukan dalam waktu O (n) , di mana n adalah ukuran list . Jadi, biaya keseluruhan untuk menambahkan elemen baru ke daftar dan menghitung median baru adalah O (n) .

3.2. Meningkatkan Pendekatan Naif

The add operasi berjalan dalam waktu linier, yang tidak optimal. Mari kita coba membahasnya di bagian ini.

Kita dapat membagi daftar menjadi dua daftar yang diurutkan - separuh lebih kecil dari bilangan bulat yang diurutkan dalam urutan menurun, dan separuh lebih besar dari bilangan bulat dalam urutan yang meningkat . Kita dapat menambahkan bilangan bulat baru ke dalam setengah yang sesuai sehingga ukuran daftar berbeda paling banyak 1, paling banyak:

if element is smaller than min. element of larger half: insert into smaller half at appropriate index if smaller half is much bigger than larger half: remove max. element of smaller half and insert at the beginning of larger half (rebalance) else insert into larger half at appropriate index: if larger half is much bigger than smaller half: remove min. element of larger half and insert at the beginning of smaller half (rebalance) 

Sekarang, kita bisa menghitung mediannya:

if lists contain equal number of elements: median = (max. element of smaller half + min. element of larger half) / 2 else if smaller half contains more elements: median = max. element of smaller half else if larger half contains more elements: median = min. element of larger half

Meskipun kami hanya meningkatkan kompleksitas waktu operasi penambahan dengan beberapa faktor konstan, kami telah membuat kemajuan.

Mari kita analisis elemen yang kita akses dalam dua daftar yang diurutkan . Kami berpotensi mengakses setiap elemen saat kami menggesernya selama operasi penambahan (diurutkan) . Lebih penting lagi, kami mengakses minimum dan maksimum (ekstrem) dari bagian yang lebih besar dan lebih kecil, selama operasi penambahan untuk penyeimbangan ulang dan selama operasi getMedian .

Kita dapat melihat bahwa ekstrim adalah elemen pertama dari daftarnya masing-masing . Jadi, kita harus mengoptimalkan untuk mengakses elemen pada indeks 0 untuk setiap paruh untuk meningkatkan waktu berjalan operasi penambahan secara keseluruhan .

4. Pendekatan Berbasis Heap

Mari perbaiki pemahaman kita tentang masalah, dengan menerapkan apa yang telah kita pelajari dari pendekatan naif kita:

  1. Kita harus mendapatkan elemen minimum / maksimum dataset di O (1) waktu
  2. Elemen tidak harus disimpan dalam urutan yang diurutkan selama kita bisa mendapatkan elemen minimum / maksimum secara efisien
  3. Kita perlu menemukan pendekatan untuk menambahkan elemen ke dataset kita yang biayanya kurang dari O (n) waktu

Selanjutnya, kita akan melihat struktur data Heap yang membantu kita mencapai tujuan secara efisien.

4.1. Struktur Data Heap

Heap adalah struktur data yang biasanya diimplementasikan dengan array tetapi dapat dianggap sebagai pohon biner .

Heap dibatasi oleh properti heap:

4.1.1. Max - properti heap

Node (anak) tidak boleh memiliki nilai yang lebih besar dari nilai induknya. Karenanya, dalam max-heap , node root selalu memiliki nilai terbesar.

4.1.2. Min - properti tumpukan

Node (induk) tidak boleh memiliki nilai yang lebih besar dari anak-anaknya. Jadi, dalam min-heap , node root selalu memiliki nilai terkecil.

Di Java, kelas PriorityQueue mewakili sebuah heap. Mari kita lanjutkan ke solusi pertama kita menggunakan heaps.

4.2. Solusi Pertama

Mari kita ganti daftar dalam pendekatan naif kita dengan dua tumpukan:

  • Min-heap yang berisi separuh lebih besar dari elemen, dengan elemen minimum di root
  • Heap maksimal yang berisi separuh lebih kecil dari elemen, dengan elemen maksimum di root

Sekarang, kita dapat menambahkan integer yang masuk ke bagian yang relevan dengan membandingkannya dengan root dari min-heap. Selanjutnya, jika setelah penyisipan, ukuran satu heap berbeda dengan heap lainnya lebih dari 1, kita dapat menyeimbangkan kembali heap tersebut, sehingga mempertahankan perbedaan ukuran paling banyak 1:

if size(minHeap) > size(maxHeap) + 1: remove root element of minHeap, insert into maxHeap if size(maxHeap) > size(minHeap) + 1: remove root element of maxHeap, insert into minHeap

Dengan pendekatan ini, kita dapat menghitung median sebagai rata-rata elemen root dari kedua heap, jika ukuran kedua heap sama. Jika tidak, elemen root dari heap dengan lebih banyak elemen adalah median .

Kami akan menggunakan kelas PriorityQueue untuk mewakili heap. Properti heap default dari PriorityQueue adalah min-heap. Kita bisa membuat max-heap dengan menggunakan Comparator.reverserOrder yang menggunakan kebalikan dari urutan natural:

class MedianOfIntegerStream { private Queue minHeap, maxHeap; MedianOfIntegerStream() { minHeap = new PriorityQueue(); maxHeap = new PriorityQueue(Comparator.reverseOrder()); } void add(int num) { if (!minHeap.isEmpty() && num  minHeap.size() + 1) { minHeap.offer(maxHeap.poll()); } } else { minHeap.offer(num); if (minHeap.size() > maxHeap.size() + 1) { maxHeap.offer(minHeap.poll()); } } } double getMedian() { int median; if (minHeap.size()  maxHeap.size()) { median = minHeap.peek(); } else { median = (minHeap.peek() + maxHeap.peek()) / 2; } return median; } }

Sebelum kita menganalisis waktu berjalan kode kita, mari kita lihat kompleksitas waktu dari operasi heap yang telah kita gunakan:

find-min/find-max O(1) delete-min/delete-max O(log n) insert O(log n) 

Jadi, operasi getMedian dapat dilakukan dalam waktu O (1) karena hanya memerlukan fungsi find-min dan find-max . Kompleksitas waktu dari operasi tambah adalah O (log n) - tiga panggilan masuk / hapus masing-masing membutuhkan waktu O (log n) .

4.3. Solusi Variasi Ukuran Tumpukan

Dalam pendekatan kami sebelumnya, kami membandingkan setiap elemen baru dengan elemen root dari heaps. Mari jelajahi pendekatan lain menggunakan heap di mana kita dapat memanfaatkan properti heap untuk menambahkan elemen baru di bagian yang sesuai.

As we have done for our previous solution, we begin with two heaps – a min-heap and a max-heap. Next, let's introduce a condition: the size of the max-heap must be (n / 2) at all times, while the size of the min-heap can be either (n / 2) or (n / 2) + 1, depending on the total number of elements in the two heaps. In other words, we can allow only the min-heap to have an extra element, when the total number of elements is odd.

With our heap size invariant, we can compute the median as the average of the root elements of both heaps, if the sizes of both heaps are (n / 2). Otherwise, the root element of the min-heap is the median.

When we add a new integer, we have two scenarios:

1. Total no. of existing elements is even size(min-heap) == size(max-heap) == (n / 2) 2. Total no. of existing elements is odd size(max-heap) == (n / 2) size(min-heap) == (n / 2) + 1 

We can maintain the invariant by adding the new element to one of the heaps and rebalancing every time:

The rebalancing works by moving the largest element from the max-heap to the min-heap, or by moving the smallest element from the min-heap to the max-heap. This way, though we're not comparing the new integer before adding it to a heap, the subsequent rebalancing ensures that we honor the underlying invariant of smaller and larger halves.

Let's implement our solution in Java using PriorityQueues:

class MedianOfIntegerStream { private Queue minHeap, maxHeap; MedianOfIntegerStream() { minHeap = new PriorityQueue(); maxHeap = new PriorityQueue(Comparator.reverseOrder()); } void add(int num) { if (minHeap.size() == maxHeap.size()) { maxHeap.offer(num); minHeap.offer(maxHeap.poll()); } else { minHeap.offer(num); maxHeap.offer(minHeap.poll()); } } double getMedian() { int median; if (minHeap.size() > maxHeap.size()) { median = minHeap.peek(); } else { median = (minHeap.peek() + maxHeap.peek()) / 2; } return median; } }

The time complexities of our operations remain unchanged: getMedian costs O(1) time, while add runs in time O(log n) with exactly the same number of operations.

Kedua solusi berbasis heap menawarkan kompleksitas ruang dan waktu yang serupa. Meskipun solusi kedua cerdas dan memiliki implementasi yang lebih bersih, pendekatannya tidak intuitif. Di sisi lain, solusi pertama mengikuti intuisi kita secara alami, dan lebih mudah untuk bernalar tentang kebenaran operasi penambahannya .

5. Kesimpulan

Dalam tutorial ini, kita belajar cara menghitung median aliran bilangan bulat. Kami mengevaluasi beberapa pendekatan dan menerapkan beberapa solusi berbeda di Java menggunakan PriorityQueue .

Seperti biasa, kode sumber untuk semua contoh tersedia di GitHub.