स्कैला के ट्रीसेट बनाम जावा के ट्रीसेट - मतदान?

Question

यदि मैं जावा के TreeSet में log(n) समय में उच्चतम प्रविष्टि को हटाना चाहता हूं, तो मैं treeSet.pollFirst() का उपयोग करता हूं - स्कैला के mutable.TreeSet कक्षा के बराबर क्या है?

वैसे भी, जो मैं वास्तव में चाहता हूं वह एक ढेर जैसी प्राथमिकता कतार डेटा संरचना है जो मुझे removeMax, add और updatePriority लॉगरिदमिक समय में देता है। मैं स्काला संग्रह पुस्तकालय को देखा और मैं उलझन में हूँ - में यह (मैं hackily स्कैन और आइटम को हटा दें और करना होगा लॉग समय में प्राथमिकता अद्यतन करने के लिए कोई रास्ता नहीं प्रदान करता है फिर से जोड़ - जबकि mutable.PriorityQueue मुझे देता है deque (यानी removeMax) लघुगणक समय में रैखिक समय)। इसी तरह mutable.TreeSet मुझे प्राथमिकता अद्यतन लघुगणक समय में लेकिन यह एक removeMax (अर्थात pollFirst) आपरेशन नहीं है (hackily को हटाने और फिर से जोड़ कर) देना होगा। मुझे किस संग्रह कंटेनर का उपयोग करना चाहिए? कृपया मुझे बाहरी निर्भरताओं के बारे में संदर्भित न करें।

Answer 1

आप और lastimmutable.TreeSet में विधियों का उपयोग कर सकते हैं, जो O(log n) हैं। एक ही तरीके का mutable.TreeSet में मौजूद हैं, लेकिन बेहतर दक्षता और परिशोधित समय (स्काला 2.10 में) प्रदान करने के लिए अधिरोहित नहीं किया गया है। head विधि लघुगणक होगा, लेकिन ऐसा करते हुए एक इटरेटर का दृष्टांत सकता है। last विधि वास्तव में इसके विपरीत है, जिसमें रैखिक जटिलता है। अच्छी खबर यह है कि आप कस्टम Ordering के साथ सबसे छोटा या सबसे बड़ा नियंत्रित कर सकते हैं - और Ordering.reverse पर कॉल करके इसे आसानी से मौजूदा Ordering से प्राप्त करें।

आप उस तत्व को दूर करने की जरूरत है, बस -= का उपयोग करें। आप पेड़ सेट पर pollFirst विधि को वापस पिग करने के लिए अपनी खुद की अंतर्निहित मूल्य वर्ग बना सकते हैं।

implicit class MyExtensions[T](ts: mutable.TreeSet[T]) extends AnyVal { 
    def pollFirst(): T = { 
    val elem = ts.head 
    ts -= elem 
    elem 
    } 
} 

Answer 2

नहीं एक जवाब, केवल एक सुझाव :) याद रखें कि आप (स्केला से जावा लाइब्रेरीज उपयोग कर सकते हैं अच्छी तरह से, अगर आप JVM :) करने के लिए संकलन इसलिए यदि जावा के TreeSet आप के लिए काम करता है, इसका इस्तेमाल :)

आप भी अपनी आवश्यकताओं को स्पष्ट कर सकते हैं; आपके अपडेट प्राथमिकता विधि के पैरामीटर क्या होंगे? किसकी प्राथमिकता आप अपडेट करने का प्रयास कर रहे हैं?