होने के रूप में एक आइटम को परिभाषित करें:अधिकतम क्लस्टर का न्यूनतम मूल्य ढूँढना?
- में एक विशिष्ट आईडी
- एक मूल्य
- एक रचना समय
- हटाने समय
मैं दो इनपुट धाराओं है - एक है कि मुझे सूचित जब कोई आइटम बनाया जाता है, तो वह आइटम जो मुझे हटा देता है जब आइटम हटा दिया जाता है। एक आइटम को कॉल करें जिसे बनाया गया है लेकिन "जीवित" नष्ट नहीं हुआ है।
मैं एक ढेर का उपयोग कर सभी जीवित आइटम के अधिकतम मूल्य ट्रैक कर सकते हैं:
whenCreated(item):
i = heap.size
heap-up(item, heap.size)
heap.size = heap.size + 1
max-value = heap[0]
whenDeleted(item):
ktem = heap[heap.size - 1]
heap.size = heap.size - 1
heap-up(ktem, index[item.id])
heap-down(ktem, index[ktem.id])
max-value = heap[0]
heap-up(item, i):
while (i > 0):
j = floor((i-1)/2)
jtem = heap[j]
if (jtem.value > item.value):
break while
index[jtem.id] = i
heap[i] = heap[i]
i = j
index[item.id] = i
heap[i] = item
heap-down(item, i):
while (2*i + 1 < heap.size):
if (2*i + 1 == heap.size or heap[2*i+1].value > heap[2*i+2].value):
j = 2*i + 1
else
j = 2*i + 2
jtem = heap[j]
if (jtem.value < item.value):
break while
index[jtem.id] = i
heap[i] = heap[i]
i = j
index[item.id] = i
heap[i] = item
मैं n आइटम मिल गया है, तो जोड़ना या हटाना एक O(log n) समय लगता है।
अब मान लीजिए कि आइटम ऐसी है कि दो आइटम, a और b, |a.value - b.value| < delta ⇒ a और b एक ही क्लस्टर में हैं दी गुच्छा बनाती हैं।
उदाहरण के लिए, अगर हम मान (1, 2, 3, 4, 7, 8, 11, 13, 14, 15, 16) और delta = 2 मिल गया है, तो समूहों (1, 2, 3, 4), (7, 8), (11), और (13, 14, 15, 16) हैं।
मैं क्लस्टर के न्यूनतम मान को ट्रैक करना चाहता हूं जिसमें अधिकतम रहने का मूल्य शामिल है। मैं इसे ढेर से मूल्यों को पढ़ने के द्वारा कर सकता हूं जब तक कि मुझे delta के बराबर आकार के मानों के बीच कोई अंतर न मिल जाए। हालांकि, यह O(n) समय लेता है, जो अपेक्षाकृत अक्षम लगता है।
क्या उस क्लस्टर के न्यूनतम मूल्य को ट्रैक करने के लिए O(log n) एल्गोरिदम है?
क्लस्टर ट्रांसमिटिव हैं? उदाहरण के लिए, यदि डेल्टा 2 है, तो एक ही क्लस्टर में 1, 2, 3, 4, 5, और 6 सभी हैं? – templatetypedef
मुझे संदेह है कि आप इसे केवल अपने वर्तमान ढेर के साथ कर सकते हैं। ऐसा लगता है कि इसे कुशलतापूर्वक करने के लिए आपको एक अलग डेटा संरचना की आवश्यकता होगी। एक अपमानजनक सेट अच्छा होगा, हालांकि आपके क्लस्टर मर्ज कर सकते हैं और फिर अनमर्ज कर सकते हैं, इसलिए आपको कुछ ऐसी चीज चाहिए जो अलगाव (जो संघ-खोज नहीं करता), उर्फ विभाजन परिष्करण की अनुमति देता है। – davin
templatetypedef का उत्तर काम करता है, हालांकि यह एक कठिन कार्यान्वयन प्रतीत होता है। यदि आप कई सीमावर्ती मामलों की अपेक्षा नहीं करते हैं तो शायद सरल 'ओ (एन) 'समाधान सार्थक है। मतलब यह है कि यह दुर्लभ होगा कि क्लस्टर का अंत अक्सर बदलता है तो यह दुनिया का अंत नहीं है। आप बीएसटी में जाकर और एक पॉइंटर को बनाए रखकर थोड़ा सुधार कर सकते हैं, और फिर आपका 'ओ (एन)' काम डिलीट पर नहीं होता है, केवल इन्सर्ट पर और फिर भी, यदि आप छोटे क्लस्टर को 'एन' के सापेक्ष उम्मीद करते हैं यह ध्यान देने योग्य नहीं होना चाहिए। – davin