مرتب سازی جدول

[sa1378]

سلام
من داشتم یه مسئله حل میکردم یه جاش باید اینکارو کنیم:
یه آرایه دوبعدی n*m داریم که تو هرخونش یه عدد ذخیره کردیم
حالا یه جای دیگه این برنامه در هر مرحله به خونه ای از این ارایه که کوچکترین عضو رو داره نیاز داریم(یعنی یه حلقه for داریم و تا زمانی که شرط برقراره هربار کوچترین عضو رو میگیره و یه کاری روش میکنه و دیگه مرحله بعد نباید ازش استفاده کرد)
اگه بخوایم در هر مرحله مینیم رو حساب کنیم میشه ( O( n^2*m^2 که خیلی زیاده (m,n<500)
پس باید اول جدول رو sort کنیم
ولی چجوری؟؟؟(میخوایم آدرس هر خونه بعد از مرتب سازی رو داشته باشیم)

[omid_kma]

نیازی به sort نیست
برای این که هر مرحله کوچترین عنصر رو داشته باشی از max heap استفاده کن .(std::priority_queue) که O هم میشه mnlogmn . برای ادرس هم می تونی محل هر خونه رو به همراه مقدار pair کنی .
اگر هم بخوای sort کنی ساده ترین راه اینه که عناصر رو بریزی توی یک آرایه یک بعدی بعد اونو مرتب کنی که از نظر اوردر با استفاده از max heap فرق نداره ولی بخاطر کپی کردن به آرایه یک بعدی کند تر میشه .

[sa1378]

نیازی به sort نیست
برای این که هر مرحله کوچترین عنصر رو داشته باشی از max heap استفاده کن .(std::priority_queue) که O هم میشه mnlogmn . برای ادرس هم می تونی محل هر خونه رو به همراه مقدار pair کنی .
اگر هم بخوای sort کنی ساده ترین راه اینه که عناصر رو بریزی توی یک آرایه یک بعدی بعد اونو مرتب کنی که از نظر اوردر با استفاده از max heap فرق نداره ولی بخاطر کپی کردن به آرایه یک بعدی کند تر میشه .

اگه بخوام بریزم تو آرایه و sort کنم آدرس هاشونو چیکار کنم؟
اگه باید pair کنم میشه بگین چجوری میشه اینو به تابع sort داد تا مرتب کنه؟

[omid_kma]

این طوری مثلا http://coliru.stacked-crooked.com/a/a8b8d63edf304b47