10
क्या हास्केल के लिए कोई फाइबोनैकी ढेर/प्राथमिकता कतार उपलब्ध है? (? या यहाँ तक कि एक asymptotically बेहतर एक) मैं this question में विभिन्न प्राथमिकता कतार कार्यान्वयन की एक सूची पाया, लेकिन मैं नहीं मिल सकता है कि उनमें से कोई फिबोनैकी ढेर की परिशोधित प्रसारण समय को संतुष्ट करता है:क्या हास्केल के लिए एक फाइबोनैकी ढेर आधारित प्राथमिकता कतार है?
- खोजें-कम से कम है ओ (1) अमूर्त समय।
- संचालन सम्मिलित करें, कुंजी घटाएं, और विलय (संघ) कार्य ओ (1) अमूर्त समय है।
- संचालन न्यूनतम हटाएं और हटाएं ओ (लॉग एन) अमूर्त समय है।
the comparison of theoretic bounds देखें।
यह संभव है कि कोई उत्पादन कोड मौजूद न हो, क्योंकि सैद्धांतिक एसिम्प्टोटिक लाभ के बावजूद निरंतर कारक सामान्य रूप से उचित आकार वाले डेटासेट के लिए द्विपदीय ढेर की तुलना में धीमी गति से फाइबोनैकी ढेर बनाते हैं। –
@ ओली चेर्लेसवर्थ दिलचस्प, क्या आप एक अनुमान लगा सकते हैं कि फिबोनाची ढेर किस आकार के फायदेमंद हो जाते हैं? –
टीबीएच, यह मेरे क्षेत्र से कुछ हद तक बाहर है; मैंने केवल इस तरह के नुकसान के बारे में पढ़ा है (उदाहरण के लिए [सीएलआरएस] (http://en.wikipedia.org/wiki/CLRS))। मुझे इस पर उद्धरण न दें;) –