পাইথনে হিপসের জন্য গাইড

পাইথনে হিপসের জন্য গাইড

ভূমিকা

প্রতি মিনিটে ফ্লাইট উড্ডয়ন এবং অবতরণ সহ একটি ব্যস্ত বিমানবন্দর কল্পনা করুন। এয়ার ট্র্যাফিক কন্ট্রোলাররা যেমন জরুরিতার ভিত্তিতে ফ্লাইটগুলিকে অগ্রাধিকার দেয়, তেমনি হিপস আমাদেরকে নির্দিষ্ট মানদণ্ডের উপর ভিত্তি করে ডেটা পরিচালনা এবং প্রক্রিয়া করতে সহায়তা করে, নিশ্চিত করে যে সবচেয়ে "জরুরি" বা "গুরুত্বপূর্ণ" ডেটা সর্বদা শীর্ষে অ্যাক্সেসযোগ্য।

এই নির্দেশিকাতে, আমরা মাটি থেকে স্তূপ বোঝার জন্য একটি যাত্রা শুরু করব। আমরা গাদা কি এবং তাদের অন্তর্নিহিত বৈশিষ্ট্য demystify করে শুরু করব। সেখান থেকে, আমরা পাইথনের নিজস্ব স্তূপ বাস্তবায়নে ডুব দেব heapq মডিউল, এবং এর কার্যকারিতার সমৃদ্ধ সেট অন্বেষণ করুন। সুতরাং, আপনি যদি কখনও ভেবে থাকেন যে কীভাবে দক্ষতার সাথে ডেটার একটি গতিশীল সেট পরিচালনা করবেন যেখানে সর্বোচ্চ (বা সর্বনিম্ন) অগ্রাধিকার উপাদানটি প্রায়শই প্রয়োজন হয়, আপনি একটি ট্রিট করার জন্য আছেন।

একটি গাদা কি?

গাদা ব্যবহারে ডুব দেওয়ার আগে আপনি প্রথম যে জিনিসটি বুঝতে চান তা হল একটি গাদা কি. একটি স্তূপ ডাটা স্ট্রাকচারের জগতে একটি গাছ-ভিত্তিক পাওয়ার হাউস হিসাবে দাঁড়িয়ে আছে, বিশেষ করে দক্ষ শৃঙ্খলা এবং শ্রেণিবিন্যাস বজায় রাখা. যদিও এটি অপ্রশিক্ষিত চোখের সাথে একটি বাইনারি গাছের সাথে সাদৃশ্যপূর্ণ হতে পারে, তবে এর গঠন এবং পরিচালনার নিয়মগুলির সূক্ষ্মতাগুলি এটিকে আলাদা করে দেয়।

একটি স্তূপের সংজ্ঞায়িত বৈশিষ্ট্যগুলির মধ্যে একটি হল এর প্রকৃতি a হিসাবে সম্পূর্ণ বাইনারি গাছ. এর মানে হল যে গাছের প্রতিটি স্তর, সম্ভবত শেষটি ছাড়া, সম্পূর্ণরূপে পূর্ণ। এই শেষ স্তরের মধ্যে, নোডগুলি বাম থেকে ডানে জমা হয়। এই ধরনের কাঠামো নিশ্চিত করে যে স্তূপগুলিকে দক্ষতার সাথে উপস্থাপন করা যেতে পারে এবং অ্যারে বা তালিকা ব্যবহার করে ম্যানিপুলেট করা যেতে পারে, অ্যারের প্রতিটি উপাদানের অবস্থান গাছে তার বসানোকে মিরর করে।

গাইড-টু-হ্যাপস-ইন-পাইথন-01.png

একটি স্তূপ প্রকৃত সারাংশ, তবে, তার মধ্যে নিহিত ক্রম। একটি মধ্যে সর্বাধিক গাদা, যে কোনো প্রদত্ত নোডের মান তার সন্তানদের মানকে অতিক্রম করে বা সমান করে, সবচেয়ে বড় উপাদানটিকে মূলে অবস্থান করে। অন্যদিকে, ক মিনিট গাদা বিপরীত নীতিতে কাজ করে: যেকোন নোডের মান হয় তার শিশুদের মানের থেকে কম বা সমান, এটি নিশ্চিত করে যে ক্ষুদ্রতম উপাদানটি মূলে বসে।

গাইড-টু-হ্যাপস-ইন-পাইথন-02.png

উপদেশ: আপনি a হিসাবে একটি গাদা কল্পনা করতে পারেন সংখ্যার পিরামিড. সর্বাধিক স্তূপের জন্য, আপনি বেস থেকে শিখরে আরোহণ করার সাথে সাথে সংখ্যাগুলি বৃদ্ধি পায়, যা সর্বোচ্চ মানের শীর্ষে পরিণত হয়। বিপরীতে, একটি মিনিম হিপ সর্বনিম্ন মান দিয়ে শুরু হয় তার শীর্ষে, আপনি নিচের দিকে যাওয়ার সাথে সাথে সংখ্যাগুলি বাড়তে থাকে।

আমরা যখন অগ্রগতি করি, আমরা আরও গভীরে ডুব দেব যে কীভাবে গাদাগুলির এই অন্তর্নিহিত বৈশিষ্ট্যগুলি দক্ষ অপারেশনগুলিকে সক্ষম করে এবং কীভাবে পাইথনের heapq মডিউল নির্বিঘ্নে আমাদের কোডিং প্রচেষ্টায় গাদা একত্রিত করে।

স্তূপের বৈশিষ্ট্য এবং বৈশিষ্ট্য

হিপস, তাদের অনন্য গঠন এবং ক্রম নীতির সাথে, স্বতন্ত্র বৈশিষ্ট্য এবং বৈশিষ্ট্যগুলির একটি সেট নিয়ে আসে যা বিভিন্ন গণনামূলক পরিস্থিতিতে তাদের অমূল্য করে তোলে।

প্রথম এবং সর্বাগ্রে, গাদা হয় সহজাতভাবে দক্ষ. তাদের গাছ-ভিত্তিক কাঠামো, বিশেষ করে সম্পূর্ণ বাইনারি ট্রি ফরম্যাট, নিশ্চিত করে যে অগ্রাধিকার উপাদানগুলির সন্নিবেশ এবং নিষ্কাশনের মতো ক্রিয়াকলাপগুলি (সর্বোচ্চ বা সর্বনিম্ন) লগারিদমিক সময়ে সঞ্চালিত হতে পারে, সাধারণত ও (লগ এন). এই দক্ষতা অ্যালগরিদম এবং অ্যাপ্লিকেশনগুলির জন্য একটি আশীর্বাদ যা অগ্রাধিকার উপাদানগুলিতে ঘন ঘন অ্যাক্সেসের প্রয়োজন।

গাদা আরেকটি উল্লেখযোগ্য সম্পত্তি তাদের মেমরি দক্ষতা. যেহেতু হিপগুলিকে অ্যারে বা তালিকা ব্যবহার করে শিশু বা পিতামাতার নোডগুলিতে স্পষ্ট পয়েন্টারের প্রয়োজন ছাড়াই উপস্থাপন করা যেতে পারে, সেগুলি স্থান-সংরক্ষণ করে। অ্যারেতে প্রতিটি উপাদানের অবস্থান গাছে তার স্থাপনের সাথে মিলে যায়, যা অনুমানযোগ্য এবং সোজা ট্রাভার্সাল এবং ম্যানিপুলেশনের জন্য অনুমতি দেয়।

স্তূপগুলির ক্রমগত বৈশিষ্ট্য, তা সর্বোচ্চ হিপ বা মিন হিপ হিসাবেই হোক, তা নিশ্চিত করে৷ রুট সর্বদা সর্বোচ্চ অগ্রাধিকারের উপাদান রাখে. এই সামঞ্জস্যপূর্ণ ক্রম পুরো কাঠামোর মাধ্যমে অনুসন্ধান না করেই শীর্ষ-অগ্রাধিকার উপাদানে দ্রুত অ্যাক্সেসের অনুমতি দেয়।

উপরন্তু, গাদা হয় বহুমুখ কর্মশক্তিসম্পন্ন. যদিও বাইনারি হিপস (যেখানে প্রতিটি পিতামাতার সর্বাধিক দুটি সন্তান রয়েছে) সবচেয়ে সাধারণ, তবে স্তূপগুলিকে সাধারণীকরণ করা যেতে পারে যাতে দুটির বেশি সন্তান থাকে, যাকে বলা হয় d-ary heaps. এই নমনীয়তা নির্দিষ্ট ব্যবহারের ক্ষেত্রে এবং কর্মক্ষমতা প্রয়োজনীয়তার উপর ভিত্তি করে সূক্ষ্ম-টিউনিং করার অনুমতি দেয়।

শেষ পর্যন্ত, গাদা হয় স্ব-সংযোজন. যখনই উপাদানগুলি যোগ করা বা সরানো হয়, কাঠামোটি তার বৈশিষ্ট্যগুলি বজায় রাখার জন্য নিজেকে পুনর্বিন্যাস করে। এই গতিশীল ভারসাম্য নিশ্চিত করে যে স্তূপটি তার মূল ক্রিয়াকলাপের জন্য সর্বদা অপ্টিমাইজ করা থাকে।

উপদেশ: এই বৈশিষ্ট্যগুলি হিপ ডেটা স্ট্রাকচারকে একটি দক্ষ বাছাই অ্যালগরিদম - হিপ সাজানোর জন্য উপযুক্ত করে তুলেছে। পাইথনে হিপ সাজানোর বিষয়ে আরও জানতে, আমাদের পড়ুন "পাইথনে গাদা সাজানো" নিবন্ধ।

আমরা পাইথনের বাস্তবায়ন এবং ব্যবহারিক প্রয়োগের গভীরে অনুসন্ধান করার সাথে সাথে, স্তূপের প্রকৃত সম্ভাবনা আমাদের সামনে উন্মোচিত হবে।

স্তূপ প্রকার

সব গাদা সমান তৈরি করা হয় না. তাদের ক্রম এবং কাঠামোগত বৈশিষ্ট্যের উপর নির্ভর করে, গাদাগুলিকে বিভিন্ন প্রকারে শ্রেণীবদ্ধ করা যেতে পারে, প্রতিটির নিজস্ব অ্যাপ্লিকেশন এবং সুবিধার সেট রয়েছে। দুটি প্রধান বিভাগ হল সর্বাধিক গাদা এবং মিনিট গাদা.

সবচেয়ে বিশিষ্ট বৈশিষ্ট্য a সর্বাধিক গাদা যে কোনো প্রদত্ত নোডের মান তার সন্তানদের মানের চেয়ে বেশি বা সমান। এটি নিশ্চিত করে যে স্তূপের বৃহত্তম উপাদানটি সর্বদা মূলে থাকে। এই ধরনের কাঠামো বিশেষভাবে উপযোগী হয় যখন নির্দিষ্ট অগ্রাধিকার সারি বাস্তবায়নের মতো ঘন ঘন সর্বাধিক উপাদান অ্যাক্সেস করার প্রয়োজন হয়।

সর্বাধিক গাদা প্রতিরূপ, a মিনিট গাদা নিশ্চিত করে যে কোনো প্রদত্ত নোডের মান তার সন্তানদের মানের থেকে কম বা সমান। এটি মূলে স্তূপের ক্ষুদ্রতম উপাদানটিকে অবস্থান করে। ন্যূনতম স্তূপগুলি এমন পরিস্থিতিতে অমূল্য যেখানে ন্যূনতম উপাদানটি প্রধান গুরুত্বের, যেমন অ্যালগরিদমগুলিতে যা রিয়েল-টাইম ডেটা প্রক্রিয়াকরণের সাথে কাজ করে।

এই প্রাথমিক বিভাগগুলির বাইরে, স্তূপগুলিকে তাদের শাখার ফ্যাক্টরের উপর ভিত্তি করে আলাদা করা যেতে পারে:

যদিও বাইনারি হিপগুলি সবচেয়ে সাধারণ, প্রতিটি পিতামাতার সর্বাধিক দুটি সন্তানের সাথে, গাদা ধারণাটি দুটির বেশি সন্তানের নোডগুলিতে প্রসারিত করা যেতে পারে। ক d-ary স্তূপ, প্রতিটি নোড সর্বাধিক আছে d শিশু এই বৈচিত্রটি নির্দিষ্ট পরিস্থিতির জন্য অপ্টিমাইজ করা যেতে পারে, যেমন নির্দিষ্ট ক্রিয়াকলাপ দ্রুত করার জন্য গাছের উচ্চতা হ্রাস করা।

দ্বিপদ স্তূপ দ্বিপদ গাছের একটি সেট যা পুনরাবৃত্তিমূলকভাবে সংজ্ঞায়িত করা হয়। দ্বিপদ স্তূপগুলি অগ্রাধিকার সারি বাস্তবায়নে ব্যবহৃত হয় এবং দক্ষ মার্জ অপারেশন অফার করে।

বিখ্যাত ফিবোনাচি ক্রমানুসারে নামকরণ করা হয়েছে ফিবোনাচির স্তূপ বাইনারি বা দ্বিপদ স্তূপের তুলনায় অনেকগুলি ক্রিয়াকলাপের জন্য আরও ভাল-অ্যামর্টাইজড রানিং টাইম অফার করে। এগুলি নেটওয়ার্ক অপ্টিমাইজেশান অ্যালগরিদমে বিশেষভাবে কার্যকর।

পাইথনের হিপ ইমপ্লিমেন্টেশন – দ্য heapq মডিউল

পাইথন হিপ অপারেশনের জন্য একটি অন্তর্নির্মিত মডিউল অফার করে - heapq মডিউল এই মডিউলটি হিপ-সম্পর্কিত ফাংশনগুলির একটি সংগ্রহ প্রদান করে যা বিকাশকারীদের তালিকাগুলিকে স্তূপে রূপান্তর করতে এবং কাস্টম বাস্তবায়নের প্রয়োজন ছাড়াই বিভিন্ন হিপ অপারেশন করতে দেয়৷ আসুন এই মডিউলটির সূক্ষ্মতা এবং কীভাবে এটি আপনাকে স্তূপের শক্তি নিয়ে আসে তা জেনে নেই।

সার্জারির heapq মডিউল একটি স্বতন্ত্র হিপ ডেটা টাইপ প্রদান করে না। পরিবর্তে, এটি এমন ফাংশন অফার করে যা নিয়মিত পাইথন তালিকায় কাজ করে, রূপান্তরিত করে এবং তাদের হিসাবে ব্যবহার করে বাইনারি গাদা.

এই পদ্ধতিটি মেমরি-দক্ষ এবং পাইথনের বিদ্যমান ডেটা স্ট্রাকচারের সাথে নির্বিঘ্নে সংহত করে।

এটার মানে হচ্ছে স্তূপগুলিকে তালিকা হিসাবে উপস্থাপন করা হয় in heapq. এই উপস্থাপনার সৌন্দর্য হল এর সরলতা - শূন্য-ভিত্তিক তালিকা সূচক সিস্টেমটি একটি অন্তর্নিহিত বাইনারি ট্রি হিসাবে কাজ করে। অবস্থানে কোনো প্রদত্ত উপাদানের জন্য i, এর:

  • বাম শিশু অবস্থানে আছে 2*i + 1
  • ডান শিশু অবস্থানে আছে 2*i + 2
  • প্যারেন্ট নোড অবস্থানে আছে (i-1)//2

গাইড-টু-হ্যাপস-ইন-পাইথন-03.png

এই অন্তর্নিহিত কাঠামো নিশ্চিত করে যে একটি পৃথক নোড-ভিত্তিক বাইনারি ট্রি উপস্থাপনার কোন প্রয়োজন নেই, যাতে অপারেশনগুলি সহজবোধ্য হয় এবং মেমরির ব্যবহার ন্যূনতম হয়।

স্পেস জটিলতা: হিপগুলি সাধারণত বাইনারি ট্রি হিসাবে প্রয়োগ করা হয় তবে চাইল্ড নোডের জন্য স্পষ্ট পয়েন্টার সংরক্ষণের প্রয়োজন হয় না। এটি তাদের একটি স্থান জটিলতার সাথে স্থান-দক্ষ করে তোলে উপর) n উপাদান সংরক্ষণের জন্য.

এটা উল্লেখ করা অপরিহার্য যে heapq মডিউল ডিফল্টরূপে মিন হিপস তৈরি করে. এর মানে হল যে ক্ষুদ্রতম উপাদানটি সর্বদা মূলে থাকে (বা তালিকার প্রথম অবস্থানে)। আপনার যদি সর্বোচ্চ হিপের প্রয়োজন হয়, তাহলে আপনাকে উপাদানগুলিকে এর দ্বারা গুণ করে ক্রম উল্টাতে হবে -1 অথবা একটি কাস্টম তুলনা ফাংশন ব্যবহার করুন।

পাইথনের heapq মডিউল ফাংশনের একটি স্যুট প্রদান করে যা ডেভেলপারদের তালিকায় বিভিন্ন হিপ অপারেশন করতে দেয়।

বিঃদ্রঃ: ব্যবহার করতে heapq আপনার অ্যাপ্লিকেশনে মডিউল, আপনাকে সহজ ব্যবহার করে এটি আমদানি করতে হবে import heapq.

নিম্নলিখিত বিভাগে, আমরা এই মৌলিক ক্রিয়াকলাপের প্রতিটির গভীরে ডুব দেব, তাদের মেকানিক্স এবং ব্যবহারের ক্ষেত্রে অন্বেষণ করব।

কীভাবে একটি তালিকাকে একটি স্তূপে রূপান্তর করা যায়

সার্জারির heapify() ফাংশন হল অনেক হিপ-সম্পর্কিত কাজের সূচনা বিন্দু। এটি একটি পুনরাবৃত্তিযোগ্য (সাধারণত একটি তালিকা) নেয় এবং একটি মিন হিপের বৈশিষ্ট্যগুলিকে সন্তুষ্ট করতে এর উপাদানগুলিকে জায়গায় পুনর্বিন্যাস করে:

সেরা-অভ্যাস, শিল্প-স্বীকৃত মান এবং অন্তর্ভুক্ত চিট শীট সহ গিট শেখার জন্য আমাদের হ্যান্ডস-অন, ব্যবহারিক গাইড দেখুন। গুগলিং গিট কমান্ড এবং আসলে বন্ধ করুন শেখা এটা!

import heapq data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
heapq.heapify(data)
print(data)

এটি একটি পুনঃক্রম তালিকা আউটপুট করবে যা একটি বৈধ মিন হিপ প্রতিনিধিত্ব করে:

[1, 1, 2, 3, 3, 9, 4, 6, 5, 5, 5]

সময় জটিলতা: ব্যবহার করে একটি স্তূপাকার মধ্যে একটি unordered তালিকা রূপান্তর heapify ফাংশন একটি উপর) অপারেশন. এটি বিপরীতমুখী মনে হতে পারে, যেমনটি কেউ এটি আশা করতে পারে O (nlogn), কিন্তু গাছের কাঠামোর বৈশিষ্ট্যের কারণে, এটি রৈখিক সময়ে অর্জন করা যেতে পারে।

হিপে একটি উপাদান কিভাবে যোগ করবেন

সার্জারির heappush() ফাংশন আপনাকে হিপের বৈশিষ্ট্যগুলি বজায় রাখার সময় স্তূপে একটি নতুন উপাদান সন্নিবেশ করতে দেয়:

import heapq heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
print(heap)

কোডটি চালানো আপনাকে মিন হিপ সম্পত্তি বজায় রাখার উপাদানগুলির একটি তালিকা দেবে:

[3, 5, 7]

সময় জটিলতা: একটি স্তূপে সন্নিবেশ অপারেশন, যা গাদা সম্পত্তি বজায় রাখার সময় স্তূপে একটি নতুন উপাদান স্থাপন করে, একটি সময় জটিলতা আছে ও (লগইন). এর কারণ হল, সবচেয়ে খারাপ ক্ষেত্রে, উপাদানটিকে পাতা থেকে মূলে যেতে হতে পারে।

স্তূপ থেকে ক্ষুদ্রতম উপাদানটি কীভাবে সরানো যায় এবং ফেরত দেওয়া যায়

সার্জারির heappop() ফাংশন স্তূপ থেকে ক্ষুদ্রতম উপাদান বের করে এবং ফেরত দেয় (এক মিনিটের স্তূপে মূল)। অপসারণের পরে, এটি নিশ্চিত করে যে তালিকাটি একটি বৈধ হিপ থাকবে:

import heapq heap = [1, 3, 5, 7, 9]
print(heapq.heappop(heap))
print(heap)

বিঃদ্রঃ: সার্জারির heappop() অ্যালগরিদমগুলিতে অমূল্য যেগুলির জন্য ক্রমবর্ধমান ক্রমে প্রক্রিয়াকরণ উপাদানগুলির প্রয়োজন হয়, যেমন হিপ সর্ট অ্যালগরিদম, বা অগ্রাধিকার সারিগুলি প্রয়োগ করার সময় যেখানে কাজগুলি তাদের জরুরিতার ভিত্তিতে কার্যকর করা হয়৷

এটি ক্ষুদ্রতম উপাদান এবং অবশিষ্ট তালিকা আউটপুট করবে:

1
[3, 7, 5, 9]

এখানে, 1 থেকে ক্ষুদ্রতম উপাদান heap, এবং বাকী তালিকাটি হিপ সম্পত্তি বজায় রেখেছে, এমনকি আমরা সরিয়ে দেওয়ার পরেও 1.

সময় জটিলতা: মূল উপাদানটি অপসারণ করা (যা একটি মিনিটের স্তূপে সবচেয়ে ছোট বা সর্বাধিক স্তূপে সবচেয়ে বড়) এবং স্তূপটিকে পুনর্গঠিত করতেও লাগে ও (লগইন) সময়।

কীভাবে একটি নতুন আইটেম পুশ করবেন এবং সবচেয়ে ছোট আইটেমটি পপ করবেন

সার্জারির heappushpop() ফাংশন একটি সম্মিলিত ক্রিয়াকলাপ যা একটি নতুন আইটেমকে স্তূপে ঠেলে দেয় এবং তারপরে পপ করে এবং স্তূপ থেকে ক্ষুদ্রতম আইটেমটি ফেরত দেয়:

import heapq heap = [3, 5, 7, 9]
print(heapq.heappushpop(heap, 4)) print(heap)

এই আউটপুট হবে 3, ক্ষুদ্রতম উপাদান, এবং নতুন প্রিন্ট আউট heap তালিকা যা এখন অন্তর্ভুক্ত 4 গাদা সম্পত্তি বজায় রাখার সময়:

3
[4, 5, 7, 9]

বিঃদ্রঃ: উপরের heappushpop() ফাংশন একটি নতুন উপাদান ঠেলাঠেলি এবং ছোট একটি আলাদাভাবে পপিং অপারেশন সঞ্চালনের চেয়ে বেশি দক্ষ।

কীভাবে সবচেয়ে ছোট আইটেমটি প্রতিস্থাপন করবেন এবং একটি নতুন আইটেম পুশ করবেন

সার্জারির heapreplace() ফাংশনটি ক্ষুদ্রতম উপাদানটিকে পপ করে এবং একটি নতুন উপাদানকে স্তূপে ঠেলে দেয়, সবই একটি কার্যকর ক্রিয়াকলাপে:

import heapq heap = [1, 5, 7, 9]
print(heapq.heapreplace(heap, 4))
print(heap)

এই প্রিন্ট 1, ক্ষুদ্রতম উপাদান, এবং তালিকায় এখন 4 রয়েছে এবং হিপ সম্পত্তি বজায় রাখে:

1
[4, 5, 7, 9]

বিঃদ্রঃ: heapreplace() স্ট্রিমিং পরিস্থিতিতে উপকারী যেখানে আপনি বর্তমান ক্ষুদ্রতম উপাদানটিকে একটি নতুন মান দিয়ে প্রতিস্থাপন করতে চান, যেমন রোলিং উইন্ডো অপারেশন বা রিয়েল-টাইম ডেটা প্রসেসিং কাজগুলিতে।

পাইথনের স্তূপে একাধিক এক্সট্রিম খুঁজে পাওয়া

nlargest(n, iterable[, key]) এবং nsmallest(n, iterable[, key]) ফাংশনগুলি একটি পুনরাবৃত্তিযোগ্য থেকে একাধিক বৃহত্তম বা ক্ষুদ্রতম উপাদান পুনরুদ্ধার করার জন্য ডিজাইন করা হয়েছে। আপনার শুধুমাত্র কয়েকটি চরম মানের প্রয়োজন হলে সেগুলি সম্পূর্ণ পুনরাবৃত্তিযোগ্য সাজানোর চেয়ে আরও দক্ষ হতে পারে। উদাহরণস্বরূপ, বলুন আপনার কাছে নিম্নলিখিত তালিকা রয়েছে এবং আপনি তালিকায় তিনটি ছোট এবং তিনটি বৃহত্তম মান খুঁজে পেতে চান:

data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

এখানে, nlargest() এবং nsmallest() ফাংশন কাজে আসতে পারে:

import heapq data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(heapq.nlargest(3, data)) print(heapq.nsmallest(3, data)) 

এটি আপনাকে দুটি তালিকা দেবে - একটিতে তিনটি বৃহত্তম মান রয়েছে এবং অন্যটিতে তিনটি ক্ষুদ্রতম মান রয়েছে data তালিকা:

[9, 6, 5]
[1, 1, 2]

কিভাবে আপনার কাস্টম গাদা নির্মাণ

যখন পাইথনের heapq মডিউল হিপগুলির সাথে কাজ করার জন্য একটি শক্তিশালী সরঞ্জাম সরবরাহ করে, এমন পরিস্থিতিতে রয়েছে যেখানে ডিফল্ট মিন হিপ আচরণ যথেষ্ট নাও হতে পারে। আপনি একটি সর্বোচ্চ হিপ প্রয়োগ করতে চাইছেন বা কাস্টম তুলনা ফাংশনগুলির উপর ভিত্তি করে কাজ করে এমন একটি গাদা প্রয়োজন, একটি কাস্টম হিপ তৈরি করা উত্তর হতে পারে। চলুন জেনে নেওয়া যাক কীভাবে নির্দিষ্ট প্রয়োজনে স্তূপ সাজানো যায়।

ব্যবহার করে একটি সর্বোচ্চ হিপ প্রয়োগ করা হচ্ছে heapq

গতানুগতিক, heapq সৃষ্টি মিনিট গাদা. যাইহোক, একটি সহজ কৌতুক দিয়ে, আপনি এটি একটি সর্বাধিক গাদা বাস্তবায়ন করতে ব্যবহার করতে পারেন। ধারণাটি হল উপাদানগুলির ক্রমকে তাদের দ্বারা গুণ করে উল্টানো -1 তাদের গাদা যোগ করার আগে:

import heapq class MaxHeap: def __init__(self): self.heap = [] def push(self, val): heapq.heappush(self.heap, -val) def pop(self): return -heapq.heappop(self.heap) def peek(self): return -self.heap[0]

এই পদ্ধতির সাহায্যে, বৃহত্তম সংখ্যাটি (পরম মানের পরিপ্রেক্ষিতে) সবচেয়ে ছোট হয়ে যায়, যা অনুমতি দেয় heapq সর্বাধিক গাদা গঠন বজায় রাখার জন্য ফাংশন।

কাস্টম তুলনা ফাংশন সহ হিপস

কখনও কখনও, আপনার এমন একটি গাদা প্রয়োজন হতে পারে যা উপাদানগুলির প্রাকৃতিক ক্রম অনুসারে তুলনা করে না। উদাহরণস্বরূপ, আপনি যদি জটিল বস্তুর সাথে কাজ করেন বা নির্দিষ্ট বাছাইয়ের মানদণ্ড থাকে তবে একটি কাস্টম তুলনা ফাংশন অপরিহার্য হয়ে ওঠে।

এটি অর্জন করতে, আপনি একটি সহায়ক শ্রেণীতে উপাদানগুলি মোড়ানো করতে পারেন যা তুলনা অপারেটরগুলিকে ওভাররাইড করে:

import heapq class CustomElement: def __init__(self, obj, comparator): self.obj = obj self.comparator = comparator def __lt__(self, other): return self.comparator(self.obj, other.obj) def custom_heappush(heap, obj, comparator=lambda x, y: x < y): heapq.heappush(heap, CustomElement(obj, comparator)) def custom_heappop(heap): return heapq.heappop(heap).obj

এই সেটআপের মাধ্যমে, আপনি যেকোনো কাস্টম কম্প্যারেটর ফাংশন নির্ধারণ করতে পারেন এবং হিপ দিয়ে এটি ব্যবহার করতে পারেন।

উপসংহার

Heaps অনেক অপারেশনের জন্য অনুমানযোগ্য পারফরম্যান্স অফার করে, যা তাদের অগ্রাধিকার-ভিত্তিক কাজের জন্য একটি নির্ভরযোগ্য পছন্দ করে তোলে। যাইহোক, হাতে থাকা অ্যাপ্লিকেশনটির নির্দিষ্ট প্রয়োজনীয়তা এবং বৈশিষ্ট্যগুলি বিবেচনা করা অপরিহার্য। কিছু ক্ষেত্রে, হিপের বাস্তবায়ন বা এমনকি বিকল্প ডেটা স্ট্রাকচার বেছে নেওয়ার ফলে বাস্তব-বিশ্বের কার্যক্ষমতা আরও ভাল হতে পারে।

গাদা, যেমন আমরা যাত্রা করেছি, কেবল অন্য ডেটা কাঠামোর চেয়ে বেশি। তারা দক্ষতা, গঠন এবং অভিযোজনযোগ্যতার সঙ্গম উপস্থাপন করে। তাদের মৌলিক বৈশিষ্ট্য থেকে পাইথনে তাদের বাস্তবায়ন পর্যন্ত heapq মডিউল, হিপস অগণিত কম্পিউটেশনাল চ্যালেঞ্জের একটি শক্তিশালী সমাধান অফার করে, বিশেষ করে যা অগ্রাধিকার কেন্দ্রিক।

সময় স্ট্যাম্প:

থেকে আরো Stackabuse